Possible cardinalities of the center of a graph¹¹1E-mail addresses: [email protected](Y.Hu), [email protected](X.Zhan).

We consider finite simple graphs. The order of a graph is its number of vertices. We denote by $V(G)$ and $E(G)$ the vertex set and edge set of a graph $G$ respectively. Denote by $d_{G}(u,v)$ the distance between two vertices $u$ and $v$ in $G.$ If the graph $G$ is clear from the context, we simply write $d(u,v).$ The eccentricity, denoted by $e(v),$ of a vertex $v$ in a graph $G$ is the distance to a vertex farthest from $v.$ Thus $e(v)={\rm max}\{d(v,u)|u\in V(G)\}.$ If $e(v)=d(v,x),$ then the vertex $x$ is called an eccentric vertex of $v.$ The radius of a graph $G,$ denoted ${\rm rad}(G),$ is the minimum eccentricity of all the vertices in $V(G),$ whereas the diameter of $G,$ denoted ${\rm diam}(G),$ is the maximum eccentricity. A vertex $v$ is a central vertex of $G$ if $e(v)={\rm rad}(G).$ The center of a graph $G,$ denoted $C(G),$ is the set of all central vertices of $G.$ A vertex $u$ is a peripheral vertex of $G$ if $e(u)={\rm diam}(G).$ A graph with a finite radius or diameter is necessarily connected. If ${\rm rad}(G)={\rm diam}(G),$ then the graph $G$ is called self-centered. Thus, a self-centered graph is a graph in which every vertex is a central vertex. A graph is called trivial if it is of order $1;$ otherwise it is nontrivial.

The central ratio of a graph $G$ is the ratio of the cardinality of its center to its order; i.e., $|C(G)|/|V(G)|.$ In 1982, Buckley [1] proved the following result.

Theorem 1. (Buckley [1]) If $c$ is a rational number with $0<c\leq 1,$ then there exists a graph whose central ratio is equal to $c.$

In this paper, we obtain more detailed information by determining which cardinalities are possible for the center of a graph with given order and radius, from which Theorem 1 follows immediately. There are unexpected phenomena in the results. We also prove a related uniqueness result.

First recall the basic fact that if $n$ and $r$ are the order and radius of a graph respectively, then $r\leq n/2.$ This can be seen by considering a spanning tree of the graph. It is well-known (e.g. [4]) that there exists a graph of radius $r$ and diameter $d$ if and only if $r\leq d\leq 2r.$

We will need the following two lemmas due to other authors.

Lemma 2. (Erdős, Saks and Sós [2, Theorem 2.1]) Every connected graph of radius $r$ has an induced path of order $2r-1.$

A cycle $C$ in a graph $H$ is called a geodesic cycle if for any two vertices $x,y\in V(C),$ $d_{C}(x,y)=d_{H}(x,y).$ Thus, a geodesic cycle is necessarily induced; i.e., it has no chords.

Lemma 3. (Haviar, Hrnčiar and Monoszová [3, Theorem 2.6]) Let $G$ be a graph of order $n,$ radius $r$ and diameter $d.$ If $n\leq 3r-2$ and $d\leq 2r-2,$ then $G$ contains a geodesic cycle of length $2r$ or $2r+1.$

Notation 1. For a positive integer $n,$  $\langle n\rangle=\{1,2,\ldots,n\},$ the set of the first $n$ positive integers.

$K_{t},$ $C_{t}$ and $P_{t}$ will denote the complete graph of order $t,$ the cycle of order $t$ and the path of order $t$ respectively. Recall that the join of graphs $G$ and $H,$ denoted $G\vee H,$ is the graph obtained from the disjoint union $G+H$ by adding the edges $xy$ with $x\in V(G)$ and $y\in V(H).$ $\overline{G}$ denotes the complement of a graph $G.$ A leaf in a graph is a vertex of degree $1.$

Notation 2. A lollipop is the union of a cycle and a path having exactly one common vertex which is an end-vertex of the path. We denote by $L(n,k)$ the lollipop of order $n$ whose cycle has length $k.$ A broom is a tree obtained by subdividing one edge of a star an arbitrary number of times. We denote by $B(n,k)$ the broom of order $n$ and diameter $k.$ If $k\leq n-2,$ the broom $B(n,k)$ has a unique vertex of degree at least $3,$ which we call the joint of the broom. The joint of the path $B(n,n-1)=P_{n}$ is defined to be the neighbor of one of the two end-vertices.

Two examples are depicted in Figure 1.

Now we are ready to state and prove the main results.

Theorem 4. Given positive integers $n$ and $r$ with $r\leq n/2,$  let $\Omega(n,r)$ denote the set of those integers $k$ such that there exists a graph of order $n$ and radius $r$ whose center has cardinality $k.$ If $n\geq 3$ then

$$\Omega(n,r)=\begin{cases}\langle n\rangle\setminus\{n-1\}\quad{\rm if}\,\,\,r\leq(3n+2)/8;\\ \{1,2,...,n-2r+2\}\cup\{6r-2n+1,...,n-2,n\}\quad{\rm if}\,\,\,(3n+2)/8<r<n/2;\\ \{2,n\}\quad{\rm if}\,\,\,r=n/2.\end{cases}$$

Proof. We first show that every value $s$ in the expression of $\Omega(n,r)$ can be attained. Note that the condition $(3n+2)/8<r$ means $(n-2r+2)+1<6r-2n+1;$ i.e., there is an integer gap between $n-2r+2$ and $6r-2n+1.$

For this part, there is no need to distinguish the case $r\leq(3n+2)/8$ and the case $(3n+2)/8<r<n/2.$ The constructions below give two graphs attaining some values of $s$ in the former case.

Suppose $r=1.$ For any $s\in\langle n\rangle\setminus\{n-1\},$ the graph $K_{s}\vee\overline{K_{n-s}}$ has order $n$ and radius $1,$ and its center has cardinality $s.$

Now suppose $2\leq r<n/2.$ We distinguish six cases.

Case 1. $s=1.$ The broom $B(n,2r)$ has order $n$ and radius $r,$ and its center has cardinality $1.$

Case 2. $2\leq s\leq n-2r+2.$ Let $G_{1}(n,r,s)$ be the graph obtained from the broom $B(n-s+2,2r-1)$ by adding $s-2$ additional vertices and joining each of them to the two central vertices of $B(n-s+2,2r-1).$ Then $G_{1}(n,r,s)$ has order $n$ and radius $r,$ and its center has cardinality $s.$ The graph $G_{1}(14,4,5)$ is depicted in Figure 2.

Case 3. $6r-2n+1\leq s\leq 2r-1$ and $s$ is odd. Then $s=2r-2k+1$ for some $k$ with $1\leq k\leq n-2r.$ If $n=2r+k,$ define the graph $G_{2}(n,r,s)$ to be the lollipop $L(n,2r).$ If $n>2r+k,$ $G_{2}(n,r,s)$ is obtained by identifying the joint of the broom $B(n-2r+1,k+1)$ with one vertex of the cycle $C_{2r}.$ Then $G_{2}(n,r,s)$ has order $n$ and radius $r,$ and its center has cardinality $s.$ The graph $G_{2}(15,4,3)$ is depicted in Figure 3.

Case 4. $6r-2n+1\leq s\leq 2r-1$ and $s$ is even. Then $s=2r-2k$ for some $k$ with $1\leq k\leq n-2r-1.$ If $n=2r+k+1,$ we identify the eccentric vertex of the unique leaf of the lollipop $L(2r+1,2r)$ with one end-vertex of the path $P_{k+1}$ to obtain the graph $G_{3}(n,r,s).$ If $n>2r+k+1,$ we identify the eccentric vertex of the unique leaf of the lollipop $L(2r+1,2r)$ with the joint of the broom $B(n-2r,k+1)$ to obtain the graph $G_{3}(n,r,s).$ Then $G_{3}(n,r,s)$ has order $n$ and radius $r,$ and its center has cardinality $s.$ The graph $G_{3}(15,4,2)$ is depicted in Figure 4.

Case 5. $2r\leq s\leq n-2.$ Then $s=2r+k-1$ for some $k$ with $1\leq k\leq n-2r-1.$ Define the graph $G_{4}(n,r,s)$ as follows. Let $C:\,x_{1},x_{2},\ldots,x_{2r}$ be a cycle of length $2r.$ Add $n-2r-k$ new vertices to $C$ and join each of them to the vertex $x_{1}$ to obtain a graph $D.$ Add $k$ new vertices to $D$ and join each of them to the two vertices $x_{2}$ and $x_{2r}$ to obtain the graph $G_{4}(n,r,s),$ which has order $n$ and radius $r,$ and whose center has cardinality $s.$ The graph $G_{4}(15,4,11)$ is depicted in Figure 5.

Case 6. $s=n.$ We obtain a graph $G_{5}(n,r)$ by adding $n-2r$ new vertices to the cycle $C:\,x_{1},x_{2},\ldots,x_{2r}$ of length $2r$ and joining each of them to the two vertices $x_{2}$ and $x_{2r}.$ Then $G_{5}(n,r)$ is a self-centered graph of order $n$ and radius $r.$ The graph $G_{5}(12,4)$ is depicted in Figure 6.

Finally suppose $r=n/2.$ We have $n=2r.$ The center of the path $P_{2r}$ has cardinality $2$ and the center of the cycle $C_{2r}$ has cardinality $n.$

Conversely, we prove that the integers appearing in the expression of $\Omega(n,r)$ are the only possible elements of the set $\Omega(n,r).$

First note that any nontrivial graph has at least two peripheral vertices. Indeed, suppose $v$ is a peripheral vertex and $u$ is an eccentric vertex of $v.$ Then both $v$ and $u$ are peripheral vertices. Thus, we always have $n-1\not\in\Omega(n,r).$

We then treat the easier case $r=n/2.$ Let $H$ be a graph of order $n$ and radius $r$ with $r=n/2.$ By Lemma 2, $H$ has an induced path $P$ of order $2r-1=n-1.$ Thus there is only one vertex $y$ outside $P.$ Since $P$ is an induced path of radius $r-1$ and $H$ has radius $r,$ the two end-vertices of $P$ are the only possible neighbors of $y.$ Hence $H$ is either a path or a cycle of the even order $n.$ Consequently the center of $H$ has cardinality $2$ or $n.$

Now we consider the case $(3n+2)/8<r<n/2.$ Let $G$ be a graph of order $n$ and radius $r$ whose center has cardinality $t.$ We will show that either $t\leq n-2r+2$ or $t\geq 6r-2n+1.$ Note that the condition $(3n+2)/8<r$ implies that $n\leq 3r-2.$ Denote by $d$ the diameter of $G.$ We distinguish two cases.

Case 1. $d\geq 2r-1.$ Let $Q$ be a diametral path of $G;$ i.e., a path of length $d$ whose end-vertices are at distance $d.$ There are two possible values of $d.$ If $d=2r,$ then there are at least $2r$ non-central vertices of $G$ on $Q.$ Hence $t\leq n-2r.$ If $d=2r-1,$ then there are at least $2r-2$ non-central vertices of $G$ on $Q.$ Hence $t\leq n-2r+2.$ In both cases we have $t\leq n-2r+2.$

Case 2. $d\leq 2r-2.$ As remarked above, we also have $n\leq 3r-2.$ By Lemma 3, $G$ has a cycle $C$ of length $2r$ or $2r+1.$ We distinguish two subcases.

Subcase 2.1. $C$ has length $2r.$ Since $2r<n,$ $G$ has vertices outside $C.$ Suppose $u_{1}v_{1}$ is a non-cut-edge of $G$ with $u_{1}\in V(C)$ and $v_{1}\not\in V(C).$ Recall that an edge is a cut-edge if and only if it belongs to no cycle [5, p.23]. Thus there is a cycle containing $u_{1}v_{1}.$ In this cycle we choose an edge $e$ such that $e\not=u_{1}v_{1}$ and $e\not\in E(C).$ Delete $e$ to obtain a new graph. If $u_{1}v_{1}$ is still a non-cut-edge of this new graph, delete an edge $f$ in a cycle containing $u_{1}v_{1}$ such that $f\not=u_{1}v_{1}$ and $f\not\in E(C).$ After finitely many such edge deletion steps, we obtain a graph $G_{1}$ containing $C$ in which $u_{1}v_{1}$ is a cut-edge.

If $G_{1}$ contains a non-cut-edge $u_{2}v_{2}$ with exactly one endpoint in $C,$ by repeating the above edge deletion procedure,we obtain a graph $G_{2}$ containing $C$ in which $u_{2}v_{2}$ is a cut-edge. Continuing this process, after finitely many steps we obtain a graph $R$ containing $C$ in which every edge with exactly one endpoint in $C$ is a cut-edge of $R.$ Suppose $u_{i}v_{i},$ $i=1,2,\ldots,p$ are all such cut-edges of $R$ with $u_{i}\in V(C).$ The vertices $v_{1},\ldots,v_{p}$ are pairwise distinct, but it is possible that $u_{i}=u_{j}$ for some pairs $i\neq j.$ Since deleting edges cannot decrease the radius of a graph, we have $r={\rm rad}(G)\leq{\rm rad}(R).$ Denote by $F_{i}$ the component of $R-u_{i}v_{i}$ containing $v_{i}.$ Then $F_{1},\ldots,F_{p}$ are pairwise vertex-disjoint.

Denote $a_{i}={\rm max}\{d_{R}(u_{i},x)|x\in V(F_{i})\},$ $i=1,\ldots,p.$ Since $C$ contains $2r$ vertices and $F_{1},\ldots,F_{p}$ are pairwise vertex-disjoint, we have $a_{1}+a_{2}+\cdots+a_{p}\leq n-2r.$ Since the order $n$ of $R$ satisfies $n\leq 3r-2,$ we deduce that $a_{i}\leq n-2r\leq r-2$ for each $i.$ It follows that $C$ contains at most $2r-(2(r-a_{i})+1)=2a_{i}-1$ vertices $y$ such that there exists a vertex $z\in V(F_{i})$ with $d_{R}(y,z)>r.$ In $R,$ altogether $C$ contains at most

$$\sum_{i=1}^{p}(2a_{i}-1)=2\left(\sum_{i=1}^{p}a_{i}\right)-p\leq 2(n-2r)-1=2n-4r-1$$

$(1)$

vertices with eccentricity larger than $r.$ Hence $C$ contains at least $2r-(2n-4r-1)=6r-2n+1$ vertices with eccentricity not exceeding $r$ in $R.$ Since $6r-2n+1\geq 6r-2(3r-2)+1=5,$ we have ${\rm rad}(R)\leq r.$ Combining this conclusion with the fact that ${\rm rad}(R)\geq r$ we obtain ${\rm rad}(R)=r;$ i.e., $R$ and $G$ have the same radius. Since $R$ is obtained from $G$ by deleting edges, every central vertex of $R$ is also a central vertex of $G.$ We deduce that $R$ and hence $G$ contains at least $6r-2n+1$ central vertices.

Subcase 2.2. $C$ has length $2r+1.$ The proof is similar to that for Subcase 2.1, but there are some differences in details. Continue using the above notations. $C$ contains at most $2\sum_{i=1}^{p}a_{i}$ vertices with eccentricity larger than $r.$ We have $2\sum_{i=1}^{p}a_{i}\leq 2(n-2r-1).$ Hence, $C$ contains at least

$$(2r+1)-2(n-2r-1)=6r-2n+3\geq 6r-2(3r-2)+3=7$$

vertices of eccentricity $r.$ Thus, $G$ has at least $6r-2n+3$ central vertices.

Combining subcases 2.1 and 2.2 we conclude that $t\geq 6r-2n+1.$ This completes the proof. $\Box$

Theorem 5. Let $n$ and $r$ be positive integers with $(3n+2)/8\leq r<n/2.$ Then the lollipop $L(n,2r)$ is the unique graph of order $n$ and radius $r$ whose center has cardinality $6r-2n+1.$

Proof. First note that the condition $(3n+2)/8\leq r<n/2$ implies that $n\geq 7,$ $n\leq 3r-2$ and $n-2r+2<6r-2n+1.$

We observe that the lollipop $L(n,2r)$ has order $n$ and radius $r,$ and its center has cardinality $6r-2n+1.$

Next suppose $G$ is a graph of order $n$ and radius $r$ whose center has cardinality $6r-2n+1.$ Denote by $d$ the diameter of $G.$ We assert that $d\leq 2r-2,$ since in the proof of Theorem 4 we have shown that if $d\geq 2r-1,$ then the center of $G$ has cardinality at most $n-2r+2,$ which contradicts the fact that the center of $G$ has cardinality $6r-2n+1.$

By Lemma 3, $G$ contains a geodesic cycle $C$ of length $2r$ or $2r+1.$ In the proof of Theorem 4 we have shown that if $C$ has length $2r+1,$ then the center of $G$ has cardinality at least $6r-2n+3,$ which contradicts our assumption. Hence $C$ has length $2r.$ Since $C$ is geodesic, it is an induced cycle. Continue using the notations in the proof of Theorem 4. Since the center of $G$ has cardinality $6r-2n+1,$ equality must hold in (1), which implies that $p=1$ and $\sum_{i=1}^{p}a_{i}=n-2r.$ Thus, in $R,$ the component $F_{1}$ is a path of order $n-2r,$ implying that $R$ is the lollipop $L(n,2r).$ Note that the center of $L(n,2r)$ has cardinality $6r-2n+1.$ If in $G$ there is an edge other than $u_{1}v_{1}$ joining a vertex of $C$ and a vertex of $F_{1},$ then the cardinality of the center of $G$ would be larger than $6r-2n+1,$ a contradiction. It follows that $G=R=L(n,2r)$ and the proof is complete. $\Box$

For example, Theorem 5 asserts that the lollipop $L(14,12)$ is the unique graph of order $14$ and radius $6$ whose center has cardinality $9.$

Finally we show that Buckley’s Theorem 1 follows from Theorem 4.

Proof of Theorem 1. Any self-centered graph, say, a cycle, has central ratio $1.$ Now let $c=a/b$ with $a<b.$ First suppose $a\neq b-1.$ Choose any positive integer $r$ with $r\leq(3b+2)/8.$ By Theorem 4, there exists a graph $G$ of order $b$ and radius $r$ whose center has cardinality $a.$ Then $G$ has central ratio $a/b.$ Next suppose $a=b-1.$ We have $2a\neq 2b-1.$ Reasoning as above, there exists a graph $H$ of order $2b$ whose center has cardinality $2a.$ Clearly $H$ has central ratio $(2a)/(2b)=c.$ $\Box$

Acknowledgement. This research was supported by the NSFC grants 11671148 and 11771148 and Science and Technology Commission of Shanghai Municipality (STCSM) grant 18dz2271000.