\documentclass[11pt]{article}
\usepackage{amsmath, amsthm, amssymb}
\usepackage[pctex32]{graphics}

\usepackage{dimacsmodules}

\setlength{\topmargin}{0in}     % top of paper to head (less one inch)
\setlength{\headheight}{0in}    % height of the head
\setlength{\headsep}{0in}       % head to the top of the body
\setlength{\textheight}{9.00in} % height of the body
\setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch)
\setlength{\evensidemargin}{0mm} % ditto, even pages
\setlength{\textwidth}{6.5in}   % width of body
\setlength{\topskip}{0in}       % top of body to bottom of first line of text
%\setlength{\footheight}{0.25in} % height of footer
%\setlength{\footskip}{0.50in}   % bottom of text to bottom of foot



\newtheorem{them}{Theorem}[section]
\newtheorem{lem}[them]{Lemma}
\newtheorem{cor}[them]{Corollary}
\newtheorem{prop}[them]{Proposition}
\newtheorem{ex}{Example}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{Definition}[them]{Definition}
\newtheorem{exercise}[them]{Exercise}
%%%%%%%%%%%%% MACROS OF AUTHORS
\def\ol{\overline}
\def\BOX{\rule{.1in}{.1in}}
\newenvironment{proof}{{\noindent\bf Proof:}}{$\BOX$ \medskip}
%\newenvironment{exercise}{\medskip\noindent}{\medskip}
\newenvironment{example}{\medskip\noindent}{\medskip}
%%%%%%%%%%%%%
\newcommand{\pinch}{\vspace{-9pt}}

\begin{document}

\begin{publicity}{}

\begin{center}

\vspace{.4in}

{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{1.0in}

{\Large \bf MODULE 08-3}\\

{\Large \bf Centrality and Anticentrality in Trees}\\

{\large \bf Date prepared: May 2008}



\vspace{.5in}

%Mathematics Department\\
%
%Annapolis, MD 21402 \\
%\\
%\\
%Val Pinciu\\
%Mathematics Department\\
%\\
%New Haven, CT 06515 \\
%

{\bf Atif Abueida}\\
{\bf University of Dayton\\
Dayton, OH 45469}\\
{\bf email: Atif.Abueida@notes.udayton.edu}\\

\bigskip

{\bf Michael Ackerman}\\
{\bf Bellarmine University\\
Louisville, KY  40205}\\
{\bf email: mackerman@bellarmine.edu}\\

\bigskip

{\bf Sul-Young Choi}\\
{\bf LeMoyne College\\
Syracuse, NY  13214}\\
{\bf email: SulYoung@lemoyne.edu}\\


\end{center}

\vfill



\end{publicity}



\newpage



\begin{center}

{\large \bf Module Description Information}

\end{center}



\begin{itemize}

\item {\bf Title:}

Centrality and Anticentrality in Trees

\item {\bf Authors:}

Atif Abueida, University of Dayton \\
Michael Ackerman, Bellarmine University \\ 
Sul-Young Choi, LeMoyne College

\item {\bf Abstract:}

The idea of the ``middle" of graphs has been studied extensively
in the literature.  In this module, we discuss different measures
of the middle of trees.  We also discuss the notion of the
``antimiddle" of a tree.  As part of our discussion of the ``antimiddle" of a tree, we 
introduce a new measure of the ``anti-middle" of a tree called the set of antiplurality 
vertices. 


\item {\bf Informal Description:}

The study of the middle of graphs has numerous real-life
applications.  The focus of this module deals with the application of locating 
a facilty such as a fire station or distribution center.  It also examines where 
to locate hazardous facilities, such as a nuclear waste site, where
the facility needs to be as far away as possible.

\item {\bf Target Audience:}

College students with discrete mathematics background.

\item {\bf Prerequisites:}

The module assumes knowledge of basic graph theory.

\item {\bf Mathematical Field:}

Graph Theory

\item {\bf Applications Areas:}

Facility location problems

\item {\bf Mathematics Subject Classification:}

Primary:  05C05; Secondary:  05C90

\item {\bf Contact Information:}

Michael Ackerman\\
Department of Mathematics\\
Bellarmine University\\
Louisville, KY  40205\\
email:  mackerman@bellarmine.edu

\item {\bf Other DIMACS modules related to this module:}

Module 03--2:  Facility Location Problems
\end{itemize}

\newpage
\section{Introduction}
One of the more interesting applications of graph theory involves facility location problems in which the following question is considered:  where is the best place to locate a fire house, an ambulance station, a distribution center, a garbage dump, or a nuclear waste facility?  In the first few situations, we wish to place the facility so that it is ``close" to all possible destinations.  In the latter two cases, we want the facility to be as far away as possible.  In this module, we examine different ways in which these questions can be answered.  For simplicity, we only use trees as our graph models; however, the ideas that we cover may also be applied to a more general graph.  Section 2 deals with the question of locating a fire house, ambulance station, or distribution center, and we examine ways to find the ``middle" of a tree.  In Section 3 we consider the ``antimiddle" of a tree to locate things such as a garbage dump or nuclear waste site.  \\

This module is designed to have the students work the exercises and answer the questions posed as they proceed through the module.  These can be done individually or discussed collectively as a class.  It is important that the students give their best effort in completing the questions and exercises before continuing with the discussion in the module. 

\section{The ``middle'' of a tree}
ZomZom University is building a new office for on-campus security.
The adminstration at ZZU is concerned with the safety of any person 
in any building on campus.  Thus, they decide to place the
new security office so that it has the smallest response time to a
complaint at any building.  Where should the security office be placed?\\

\noindent We model the campus map using a graph where the vertices
of the graph represent the buildings on campus, and the edges of
the graph represent the walkways between buildings.  For
simplicity sake, we use a tree to depict the ZZU campus, which appears in Figure \ref{ZZUcampus1}.\\


%\vspace*{2.5in}%% Insert Figure 1
%\vskip0.2truecm
\begin{figure}[h]
%\hspace{1.0in}\input{ZZUfig1.latex}
\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil

\caption{A tree model of ZZU's campus}
\label{ZZUcampus1}
\end{figure}
%\vskip0.6truecm


\noindent Before we begin our discussion, we review some graph theoretic terms.  The number of vertices in a graph $G$ is called the {\bf order} of $G$.  A {\bf {\it u}-$v$ path} in a graph $G$ is a finite, alternating sequence of vertices and edges of $G$, beginning at the vertex $u$ and ending at the vertex $v$, in which no vertex is repeated.  We typically denote a path using only the vertices in the sequence.  For example, for the path $a,(a,e),e,(e,f),f,(f,g),g$ in Figure \ref{ZZUcampus1}, we simply write $a \, e \, f \, g$.  A path whose beginning and ending vertices are the same is called a {\bf cycle}.  A graph which contains no cycles is a {\bf tree}.  If there is a path between every pair of distinct vertices in a graph $G$, we say that $G$ is a {\bf connected graph}.  Otherwise, $G$ is {\bf disconnected}.  A {\bf component} of $G$ is a subgraph of $G$ that is connected and is not properly contained in any connected subgraph of $G$.\\

\noindent  The {\bf degree} of a vertex $u$ in $G$, denoted $deg(u)$, is the number of vertices to which $u$ is adjacent in $G$.  If $deg(u)=1$, then $u$ is called an {\bf endvertex}.  Finally, let $u$ and $v$ be vertices of $G$.  The {\bf distance between $u$ and $v$}, denoted $d(u,v)$, is the length of a shortest $u$-$v$ path.\\

\noindent For example, referring to the connected graph of order 6 in Figure \ref{graphex}, $e \, d \, c \, b$ is a path while $e \, d \, c \, d \, a$ is not a path.  The vertices $e$ and $f$ are endvertices, and $a \, b \, c \, d \, a$ is a cycle.  The degree of $b$ is 3, and the distance between $a$ and $f$ is 2.

\begin{figure}[h]
\hfil\scalebox{0.75}{\includegraphics{ZZUfig2.eps}}\hfil
\caption{An example graph}
\label{graphex}
\end{figure}

\noindent Those wanting a more detailed discussion of graph theoretic terms are encouraged to consult Chartrand and Lesniak \cite{cl}.\\

\noindent Returning to the tree that models ZZU at which vertex do you think the security office should be placed?  Why?\\

%\begin{figure}[h]
%\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil
%\caption{A tree model of ZZU's campus}
%\label{ZZUcampus2}
%\end{figure}

\noindent Let us formally define the terms used in this process.\\

\noindent Let $x$ be a vertex in the graph $G$. The {\bf
eccentricity of $x$}, denoted by $e(x)$, is the distance to a
vertex farthest from $x$. More formally, ${\displaystyle e(x)=
\max_{y \in V(T)} \{d(x,y)\}}$.  The {\bf radius of $G$}, denoted
by $rad(G)$, is the minimum eccentricity of the vertices of $G$
while the {\bf diameter of $G$}, denoted by $diam(G)$, is the
maximum eccentricity of the vertices of $G$.  Note that the length
of the longest path in a tree is the diameter of the tree.\\


\noindent Go back and label each vertex in Figure \ref{ZZUcampus1} with its
eccentricity.\\

\noindent After labelling the eccentricities of the vertices, did you get $f$ as the vetex with smallest eccentricity?  We refer to the set containing the vertex
$f$ as the center of the tree.


\begin{Definition}
The set of vertices of a graph $G$ with minimum eccentricity is called the {\bf
center of $G$}.
\end{Definition}

\newpage
\begin{exercise}  
Find the center of each tree given below.
\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{ZZUfig4.eps} \hspace*{4cm} \includegraphics{ZZUfig5.eps}}\hfil
\label{ZZUcampus}
\end{figure}
\vskip2.0truecm

\noindent Now, we consider a couple properties about the center of a
tree.  Additional properties of the center of a tree are left as exercises at the end of the section.

\begin{prop}
The center of a tree T is contained on every longest path.
\end{prop}

\vspace{.1in} \noindent Notice that in the examples above, the
center was either a single vertex or two adjacent vertices.  This
result is true for any tree.  The proof of which is left as an exercise.

\begin{them}
The center of a tree T consists of one vertex or two adjacent
vertices.
\end{them}
%\vspace{.1in}

\noindent Now, we turn our attention back to the campus in our
original example.  A take-out Chinese restaurant receives
permission to open a restaurant to exclusively serve the entire
campus. Since the patrons on campus are very busy, the bulk of the
restaurant's business will be from delivery service. Where should
the restaurant be located?  In this situation many trips will be
made from the restaurant to the buildings on campus. Therefore, we want to
minimize the sum of the distances from the restaurant to these
buildings.

\begin{Definition}
The {\bf status} $s(x)$ of a vertex x in a graph G is the sum of
all distances from each vertex of $G$ to x ${\displaystyle
\left( {\rm i.e.,} \;\; s(x) = \sum_{y \in V(G)} d(x,y)\right)}$.
\end{Definition}

\noindent Label each vertex of our campus tree in Figure \ref{ZZUcampus3} with its status.

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.70}{\includegraphics{ZZUfig1.eps}}\hfil
\caption{A tree model of ZZU's campus}
\label{ZZUcampus3}
\end{figure}
\vskip0.2truecm

\newpage
\noindent We are looking for the vertices with smallest status.


\begin{Definition}
The set of vertices of the graph $G$ with minimum status is called the {\bf median
of $G$}.
\end{Definition}

\noindent So which set of vertices is the median of the tree in Figure \ref{ZZUcampus3}?\\

%\newpage
\vspace*{.1in}
\begin{exercise}  
Find the median for the trees given below. 
\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
%\hspace{1.0in}\input{ZZUfig1.latex}
\hfil\scalebox{0.55}{\includegraphics{ZZUfig4.eps} \hspace*{4cm} \includegraphics{ZZUfig5.eps}}\hfil
%\label{}
\end{figure}
\vskip0.6truecm

\noindent Notice that the center and the median of the right-most tree in the above exercise are disjoint.  In fact, the center and median of a tree can be arbitrarily far apart.\\


\noindent As you probably discovered by now, calculating the status of each vertex of a tree $T$ to find the median of $T$ becomes quite complicated as the vertex set of $T$ becomes larger.  We now examine a procedure to find the median of a tree without having to calculate the status of a vertex.  First, we need some preliminaries.

\begin{Definition}
Let $x$ and $y$ be vertices in a tree $T$.  Define $V_{xy}$ to be
the set of vertices of T that are closer to $x$ than to $y$
$\displaystyle{\left( i.e., \;\; V_{xy}=\{z \in V(T)|
d(x,z)<d(y,z)\}\right)}$.
\end{Definition}

\noindent For example, in the tree in Figure \ref{ZZUcampus3}, $V_{ch} = \{c,b,a,d,e\}$ and $V_{hc} = \{h,g\}$.

\noindent We have the following lemma.
\begin{lem} \label{median1}
If xy is an edge in a tree T, then $$s(x)=s(y) + |V_{yx}| -
|V_{xy}|.$$
\end{lem}

\vspace*{.1in}

\begin{exercise}  
Verify the status of vertex $i$ in Figure \ref{ZZUcampus3} using the previous lemma.
\end{exercise}

\vspace{.2in}

\noindent Now, we discuss a procedure to find the median of a tree called the Majority Strategy, which was developed by H.M. Mulder in \cite{mul}.
\vspace{.2in}

\noindent {\bf The Majority Strategy}
    \begin{enumerate}
    \item Start at an initial vertex $x_1$ in the tree $T$.
    \item For each $i \geq 1$,
    move from $x_i$ to $x_{i+1}$ where $x_{i+1}$ is a vertex
    satisfying:
        \begin{enumerate}
        \item[(i)] $x_i$ and $x_{i+1}$ are adjacent,
        \item[(ii)] $\displaystyle{|V_{x_{i+1},x_i}| \geq |V_{x_i, x_{i+1}}|}$ , and
        \item[(iii)] $x_{i+1} \neq x_j$ for any $j < i$.
        \end{enumerate}
    \item Stop when there are no more vertices into which to move.
    \end{enumerate}

Let $x_p$ be the last vertex when the above process is applied.
Then either
    \begin{enumerate}
    \item[(i)] for all vertices $v$ with $d(x_p, v)=1$, $|V_{v, x_p}| <
    |V_{x_p, v}|$, or
    \item[(ii)]  if $v$ is a vertex $d(x_p, v)=1$
    and $\displaystyle{|V_{v,x_p}| \geq |V_{x_p, v}|}$, then $v=x_j$
    for some $j < p$.  In this case, $v_j = x_{p-1}$ since $T$ does not contain a cycle.
    \end{enumerate}

In the first case above, the median is $\{x_p\}$ while $\{x_{p-1}, x_p\}$ is the median in the second case.

\noindent From the examples that we have considered, it appears that the median of $T$ is a single vertex or two adjacent vertices.  Indeed, this is true in general.

\begin{them}
The median of a tree T consists of one single vertex or two
adjacent vertices.
\end{them}
\begin{proof}
Use the Majority strategy discussed above. 
\end{proof}

\vspace{.2in}
\noindent We continue with another way to define the ``middle" of a tree $T$ in which we examine the size of the components of $T$ after deleting a vertex.

\begin{Definition}
Let $T$ be a tree and let $x$ be a vertex of $T$.  The {\bf branch weight of $x$}, denoted $bw(x)$, is the number of vertices in a largest component of $T-\{x\}$.
\end{Definition}

%\begin{exercise} 
\noindent Label each vertex in Figure \ref{ZZUcampus4} with its branch weight.
%\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil
\caption{A tree model of ZZU's campus}
\label{ZZUcampus4}
\end{figure}
\vskip0.2truecm

\noindent We are looking for the set of vertices of smallest branch weight, which is called the centroid of $T$.

\begin{Definition}
The set of all vertices of a tree $T$ that have minimum branch
weight is called the {\bf centroid of $T$}.
\end{Definition}
%\newpage
\noindent In the example above, the centroid($T$) is the set
containing the vertex $f$.\\

\newpage
\begin{exercise} 
Find the centroid of the following trees.
\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
%\hspace{1.0in}\input{ZZUfig1.latex}
\hfil\scalebox{0.55}{\includegraphics{ZZUfig4.eps} \hspace*{5cm} \includegraphics{ZZUfig5.eps}}\hfil
%\label{}
\end{figure}
\vskip0.6truecm


\noindent How does the centroid for the trees in the
previous examples compare to the median for each of those trees? \\

\noindent This observation leads us into our next theorem. \vspace*{.1in}

\begin{them}
In a tree $T$, the median of $T$ equals the centroid of $T$.
\end{them}

\noindent Before we begin the proof of the theorem, we introduce two useful lemmas.

\begin{lem}
Let $xy$ be an edge in a tree.   Then
\begin{enumerate}
\item[(i)] if $bw(x) < bw(y)$, then $s(x)< s(y)$.
\item[(ii)] if $bw(x) = bw(y)$, then $s(x) =s(y)$.
\end{enumerate}
\end {lem}

\begin{proof}
\noindent
Let $\{B_{x1}, B_{x2}, ..., B_{xp}\}$ be the set of branches of $x$ and  $\{B_{y1}, B_{y2}, ..., B_{yq}\}$ the set of branches of $y$.  Without loss of generality, we may suppose that $B_{x1}$ contains $y$, and $B_{y1}$ contains $x$.  Then $V(B_{x1}) = V_{yx}$, $V(B_{y1}) = V_{xy}$, $B_{yi}$ is a subgraph of $B_{x1}$ for all $i >1$, and  $B_{xj}$ is a subgraph of $B_{y1}$ for all $j >1$.  

\vspace {.1in}
\noindent
Suppose $bw(x) < bw(y)$, but $s(x)\geq s(y)$.  From Lemma \ref{median1} and our assumption, $|V_{yx}| - |V_{xy}|= s(x) - s(y) \geq 0$.  From the paragraph above, we have that for all $j>1$, $|V(B_{xj})| < |V_{xy}| \leq |V_{yx}| = |V(B_{x1})|$ and $bw(x)= |V(B_{x1})|=|V_{yx}|$. Since $bw(y) = max \{|V(B_{yi})|: i=1,2, \dots. q\} \leq  max \{|V_{xy}|, |V_{yx}| - 1\} \leq |V_{yx}|$, we have that $bw(y) \leq bw(x)$, a contradiction.  Therefore, $bw(x) < bw(y)$ implies $s(x) < s(y).$

\vspace{.1in}
\noindent
Suppose that $bw(x) = bw(y)$, but $s(x) \not= s(y)$.  Without loss of generality we may assume $s(x) > s(y)$.  Using a similar argument we can deduce that $bw(x) = |V_{yx}|$, $bw(y) <|V_{yx}|$, and $bw(x) < bw(y)$. Therefore, $bw(y) = bw(x)$ implies $s(x) = s(y).$
\end{proof}

\vspace {.2in}

\noindent
From the above lemma, we conclude that for two adjacent vertices $x$ and $y$ in a tree,
\begin{enumerate}
\item[(i)] $bw(x) < bw(y)$ if and only if $s(x)< s(y)$, and
\item[(ii)] $bw(x) = bw(y)$ if and only if  $s(x)=s(y)$.
\end{enumerate}

\noindent The converse of Lemma 2.12 is left as an exercise.

\vspace {.2in}
\begin{lem} \label{pathlem}
\noindent
Let $x, y,$ and $z$ be three vertices in a tree $T$ such that $d(x,z)=d(x,y)+d(y,z)=2$.  Then: 
\begin{enumerate}
\item[(i)] $V_{xy} \subset V_{yz}$ and $V_{zy} \subset V_{yx}$
\item[(ii)] If $s(x) \leq s(y)$, then $s(y) < s(z).$  
\item[(iii)]Also, if $bw(x) \leq bw(y)$, then $bw(y) < bw(z)$.
\end{enumerate}
\end{lem}

\begin{proof}
\noindent
\begin{enumerate}
\item[(i)] Exercise. 
 
%%I would like to add this as an exercise%%

\item[(ii)]
Since $xy$ is an edge in $T$, $s(x)-s(y)=|V_{yx}|-|V_{xy}|$ from Lemma \ref{median1}, and thus, $|V_{yx}|\leq |V_{xy}|$.  From (i), $|V_{zy}| < |V_{yx}| \leq |V_{xy}| < |V_{yz}|$.  So $s(y)-s(z)=|V_{zy}|-|V_{yz}| < 0$.
\item[(iii)]  From (ii) and previous Lemma.
\end{enumerate}
\end{proof}

\vspace {.2in}
\noindent
As a result of the previous lemma, if $P=u_1 \, u_2 \, \dots \, u_q$   
is a path in a tree $T$ and $s(u_1) \leq s(u_2)$ (or $bw(u_1) \leq bw(u_2)$), then $s(u_i) < s(u_j)$ (or $bw(u_i) < bw(u_j)$) for all $i$ and $j$ with $i<j$ and $j > 2$.  

\vspace {.2in}

\noindent Now, we are ready to prove the theorem.\\
\begin{proof}
Suppose that the median of $T$ consists of two adjacent vertices $x$ and $y$.  Then $s(x)=s(y)$ and $bw(x)=bw(y)$.
For a vertex $u$ not in the median of $T$, since  $x$ and $y$ are adjacent in a tree, there exists a path $P$ containing three vertices $x$, $y$, and $u$.  Without loss of generality we may assume that $P$ is the $x-u$ path.  From the previous Lemma, $s(x) < s(u)$ and $bw(x) < bw(u)$.  This imples that $Centroid(T) = \{x,y\}$.

\vspace {.1in}
\noindent
The case that the median of $T$ consists of only one vertex can be proven using a similar argument.
\end{proof}
  
\vspace*{.1in}

\noindent A consequence of the previous theorem is that the centroid of any tree consists of a single
vertex or two adjacent vertices.\\

\noindent Next, we investigate our final way to determine the
``middle" of a tree by pruning leaves from the tree in a particular order.

\begin{Definition} A {\bf processing sequence for a tree $T$ of order $n$} is a permutation
$(x_1,x_2, \dots, x_n)$ so that $x_1$ is an endvertex of $T$ and
for $2 \leq j \leq n$, $x_j$ is an endvertex of $T-\{x_1,x_2,
\dots, x_{j-1}\}$.
\end{Definition}


\begin{exercise} 
For the tree $T$ in Figure \ref{ZZUcampus5}, verify the following sequences are processing sequences for $T$:
\end{exercise}
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil
\caption{A tree model of ZZU's campus}
\label{ZZUcampus5}
\end{figure}
%\vskip0.6truecm

$$P_1=(a,j,d,h,g,k,i,f,b,c,e)$$
$$P_2=(h,g,j,k,i,f,c,b,d,a,e)$$
$$P_3=(a,b,c,d,e,h,j,k,i,f,g)$$\\

%\vspace*{.2in}
\noindent Can you come up with a processing sequence in which the
vertex $e$ appears sooner than the fifth entry?\\


\noindent In fact, the fifth entry is the earliest that the vertex
$e$ can appear in a processing sequence.


\vspace*{.2in}
\begin{Definition} Let x be a vertex in tree T.  The {\bf processing
number} of x, denoted by $proc(x)$, is the earliest entry at which
x occurs in a processing sequence (i.e., $proc(x)=\min \{i |
x=x_i$ in some processing sequence of $T$\}).
\end{Definition}

\vspace*{.1in}
\begin{Definition} The {\bf processing center} of T is the set of vertices of T with
maximum processing number.
\end{Definition}

%\begin{exercise}
\noindent Find the processing number of each vertex and the processing center for the tree in Figure \ref{ZZUcampus6}.  
%\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil
\caption{A tree model of ZZU's campus}
\label{ZZUcampus6}
\end{figure}
\vskip0.6truecm

\noindent How do the branch weights and processing numbers of each
vertex in the tree above compare?  \\

\noindent This leads us to our next proposition.  

\vspace{.1in}
\begin{prop}
\label{procnum/bw}
For a vertex v in a tree T,  $proc(v)= |V(T)|
- bw(v)$.
\end{prop}

\begin{proof}
Suppose that $(x_1,x_2, \dots, x_n)$ is a processing sequence of a tree $T$.  
From the definition of processing sequence, the subgraph induced by $T-\{x_1,x_2,
\dots, x_{j-1}\}$ is connected.  So the subgraph induced by $\{x_{j+1},x_{j+2}, \dots, x_n\}$ is a branch of $x_j$ in $T$. 

For a vertex $v$ in $T$, let $(x_1,x_2, \dots, x_n)$ be a processing sequence corresponding to $proc(v)$.  Then $v=x_j$ for some $j$, and the subgraph induced by $\{x_{j+1},x_{j+2}, \dots, x_n\}$ is the largest branch of $v$ in $T$.  Thus, $proc(v)=j=n-(n-j)=|V(T)|- bw(v)$.  
\end{proof}

\vspace{.1in}
\begin{exercise}  
Find the processing center for the following trees.
\end{exercise}
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{ZZUfig4.eps} \hspace*{4cm} \includegraphics{ZZUfig5.eps}}\hfil
%\label{}
\end{figure}
\vskip0.6truecm

\noindent How does the processing center found for the trees in
the previous examples compare to the median(centroid)? \\

\noindent This leads us to our next theorem.
\vspace*{.1in}

\begin{them}
In a tree $T$, the processing center of T is the same as the median
of $T$.
\end{them}
\begin{proof}
From Proposition \ref{procnum/bw}, we know that $proc(u)= |V(T)|-bw(u)$ for each vertex $u$ in $T$.  By definition, the processing center of $T$ is ${\displaystyle \max_{u \in V(T)} \{proc(u)\} = 
\max_{u \in V(T)} \{|V(T)|-bw(u)\}}$.  Since $|V(T)|$ is constant, the right-hand side of the equation above is maximized when $bw(u)$ is minimized.  Thus, the processing center of $T$ is the same as the centroid of $T$.  Therefore, the processing center of $T$ is the same as the median of $T$.  
\end{proof}

\noindent As a result of the previous theorem, the processing center of a tree $T$ consists of a
single vertex or two adjacent vertices. \vspace*{.1in}

\noindent Note that there are other ways to find the ``middle" of
a tree. If you would like to investigate some of these other ways,
do not hesitate to visit your friendly professor.

\vspace*{.2in}

\noindent {\bf Additional Exercises}
\begin{enumerate}
\item Let $G$ be a connected graph.  Prove that $rad(G) \leq diam(G) \leq 2rad(G)$.
For each inequality above, give an example of a graph of order greater than 2 where
equality holds.\\
\item Let $r$ and $d$ be fixed positive integers where $r \leq d
\leq 2r$. Construct a graph with radius $r$ and diameter $d$.\\
\item Let $x$ and $y$ be vertices of the graph $G$.  Prove that $|e(x)-e(y)| \leq d(x,y)$.
\item Show that the center of a tree T is contained on every longest path.\\
\item Find the center, median, centroid, and processing center for the given tree.\\
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{ZZUfig13.eps}}\hfil
\end{figure}
\vskip0.2truecm
\item Prove that the center of a tree is a single vertex or two adjacent vertices.\\
\item Show that a tree $T$ has just a single vertex as its
center if and only if $diam(T)=2rad(G)$.\\
\item Construct a tree in which the center and median are
arbitrarily far apart. Can this be done so that both contain two vertices? \\
\item Prove Lemma \ref{median1}. \\
\item Let $xy$ be an edge in a tree $T$.  Prove that:\\
\hspace*{12pt} (a)  if $s(x) < s(y)$, then $bw(x) < bw(y)$ \\
\hspace*{12pt} (b)  if $s(x) = s(y)$, then $bw(x) = bw(y)$\\
\item Prove Lemma \ref{pathlem} (i).\\
%\item Show that for any vertex $v$ in $T$, $n-1 \leq s(v) \leq
%\frac{(n-1)(n+2)}{2}-(n-1)$.
\end{enumerate}


\newpage
\section{The ``antimiddle" of trees}

Returning the beautiful campus of ZomZom University, they now have
quite an accumulation of garbage that is making the campus
unattractive.  So, the administration approved a huge dumpster
directly behind one of the buildings on campus to collect all of
the campus' garbage.  Where should the dumpster be located?

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.75}{\includegraphics{ZZUfig1.eps}}\hfil
\caption{A tree model of ZZU's campus}
\label{ZZUcampus7}
\end{figure}
\vskip0.6truecm

\noindent In this application we want to put the dumpster ``as far
away" as possible.  Initially, we are interested in those vertices
having maximum eccentricity.

\begin{Definition} Let T be a tree.  The {\bf anticenter of $T$} is the
set of vertices with maximum eccentricity.
\end{Definition}

\noindent From the definition of anticenter, we obtain the following proposition.

\begin{prop}
The anticenter of a tree $T$ is the set of end vertices on the longest paths of $T$.
\end{prop}

\noindent If we refer to the eccentricities of the vertices that we found in Section 2, the anticenter of $T$ is
$\{a,b,c,d,h,j,k\}$.  However, this poses a problem.  How do we decide among these 7 
vertices where to put the huge dumpster?\\

\noindent Let us examine another notion of ``anticentrality".  In
this situation we are looking for those vertices whose status is
as large as possible.

\begin{Definition} Let T be a tree.  The {\bf antimedian of $T$} is the
the set of vertices with maximum status.
\end{Definition}

\noindent Consulting our previous work in which we found the status of each vertex in the tree
in Figure \ref{ZZUcampus7}, we see that the
vertex $h$ has the maximum status.  Thus, the antimedian of $T$ is
$\{h\}$, and in this case, the antimedian makes the decision of where to place the dumpster much easier.\\
\newpage
\begin{exercise}  
Find the anticenter and antimedian of the trees below.
\end{exercise}

\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.45}{\includegraphics{antiplurex1.eps} \hspace*{3cm} \includegraphics{antiplurex2.eps}}\hfil
%\label{}
\end{figure}
\vskip0.2truecm

\noindent From the previous exercise, we notice that an antimedian vertex of a tree is not necessarily on a longest path.  Thus, an antimedian vertex is not necessarily an anticenter vertex.  A natural question arises:  How do the antimedian and anticenter of a tree compare?  In \cite{johns}, Johns shows that they can be made arbitrarily far apart.  We omit the proof of the theorem but illustrate the idea using the tree below where $k \geq 5$ and ${\displaystyle m=\frac{k^2-5k+10}{2}}$.

\vskip0.3truecm
\begin{figure}[h]
\hfil\scalebox{0.60}{\includegraphics{antimedcent.eps}}\hfil 
\end{figure}
\vskip0.3truecm

\noindent In the tree above, one should verify that $e(v)=k$ and $e(u)=2k-4$.  So the anticenter contains all $2k$ vertices at either end of the tree.  However, $s(v)=k^3-4k^2+9k-3$ and $s(u)=k^3-4k^2+8k-3$.  Thus, the antimedian contains only the vertex $v$.  \\

\noindent We employ one other strategy to determine ``antimiddle" vertices in a tree.

\begin{Definition} Let T be a tree.  The vertex x is an
{\bf antiplurality vertex of $T$} if and only if $|V_{xy}| \leq
|V_{yx}|$ for all y in V(T).
\end{Definition}

\noindent It is obvious from the definition that an antiplurality vertex of a tree is an end vertex.

\newpage

\begin{exercise}  
Find all antiplurality vertices for the trees below.
\end{exercise}
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{ZZUfig1.eps}}\hfil \\ 
\hfil\scalebox{0.45}{\includegraphics{antiplurex1.eps} \hspace*{3cm} \includegraphics{antiplurex2.eps}}\hfil
\end{figure}
\vskip0.6truecm

\noindent For the trees in the previous exercise, there does not appear to be any obvious relationship between the antimedian and the set of antiplurality vertices in a tree.  In fact, an antimedian vertex and an antiplurality vertex can be arbitrarily far apart (See Exercise 3 in this section).  However, by examining the examples above, it seems that an antiplurality vertex is an anticenter vertex.  The next proposition confirms that notion.

\begin{prop}
In a tree $T$, an antiplurality vertex of $T$ is an endvertex on a longest path in $T$
\end{prop}
\begin{proof}
Suppose that $u$ is an antiplurality vertex but not an endvertex on any longest path in the tree $T$.  Let $P$ be a longest path in $T$ with endvertices $x$ and $y$, and let $w$ be the vertex on $P$ such that $d(u,w)=\min \{d(u,v)| v \;$ is on the $u$-$x$ path$\}$.  Since $P$ is a longest path in $T$, $d(u,w) < d(x,w)$, and $d(u,w) < d(w,y)$.  This means that $V_{xu} \subsetneq V_{uy}$ and $V_{yu} \subsetneq V_{ux}$.  Since $u$ is an antiplurality vertex, $|V_{ux}| \leq |V_{xu}|$.  So we have that $|V_{yu}| < |V_{ux}| \leq |V_{xu}| < |V_{uy}|$ which contradicts the fact that $u$ is an antiplurality vertex.   Thus, $u$ is an endvertex on a longest path in $T$.  
\end{proof}

\noindent There are other ways to determine the ``antimiddle" of a tree
$T$.  If you would like to investigate some of these other ways, do not
hesitate to visit your friendly professor.

\newpage 
\noindent{\bf Additional Exercises}
\begin{enumerate}
\item Find the anticenter, antimedian and all antiplurality vertices for the given tree. \\
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{ZZUfig17.eps}}\hfil
\end{figure}
\vskip0.6truecm

\item Construct a tree of order at least 5 whose anticenter, antimedian, and antiplurality vertices are the same. \\
\item For the following tree, determine the anticenter, antimedian and antiplurality vertices for several values of $k$ and $m$.  Find the value of $k$ and $m$ for which the distance between an antimedian vertex and an antiplurality vertex (or an anticenter vertex) is at least 9. \\
\vskip0.2truecm
\begin{figure}[h]
\hfil\scalebox{0.55}{\includegraphics{antiplexercise.eps}}\hfil
\end{figure}

\end{enumerate}

\newpage

\begin{thebibliography}{99}
\bibitem{b} F. Buckley, ``Facility location problems", College Math. J.
18 (1987), 24-32.
\bibitem{bh} F. Buckley and F. Harary, {\it Distance in Graphs},
Addison-Wesley Publ. Co, New York (1990).
\bibitem{cl}  G. Chartrand and L. Lesniak, {\it Graphs and
  Digraphs}, Chapman \& Hall, London (1996).
\bibitem{johns} G. Johns, ``Margins in graphs and trees", Congr. Numer. 134 (1998), 99-105. 
\bibitem{l} M. Labbe,``Location of an obnoxious facility on a network: a
voting approach", Networks 20 (1990), 197-207.
\bibitem{min} E. Minieka, ``Anticenters and antimedians of a network", Networks 13 (1983), 359-364.
\bibitem{mul} H.M.Mulder, ``The majority strategy on graphs", Discrete
Applied Math. 80 (1997), 97-105.
\bibitem{z} B. Zelinka, ``Medians and peripherians of trees", Arch. Math. (Brno) 4 (1968), 87-95.
\end{thebibliography}


\end{document}
