Graphs with a Fixed Maximum Degree and Order Attaining the Upper Bound on Minimum Status

Abstract

The status (or transmission) of a vertex in a connected graph is the sum of distances between the vertex and all other vertices. The minimum status (or minimum transmission) of a connected graph is the minimum of the statuses of all vertices in the graph. Previously, sharp lower and upper bounds have been obtained on the minimum status of connected graphs with a fixed maximum degree k and order n. Moreover, for $2\le k\le {\displaystyle \frac{n}{2}}$, the following theorem about graphs attaining the maximum on the minimum status has also been proposed without proof. The theorem is as follows: Let G be a connected graph of order n with $▵(G)=k$, where $2\le k\le {\displaystyle \frac{n}{2}}$. Then, the minimum status of G attains the maximum if and only if one of the following holds. (1) G is a path or a cycle, where $k=2$; (2) $G_{k,n}$ is a spanning subgraph of G and G is a spanning subgraph of $H_{k,n}$, where $3\le k<{\displaystyle \frac{n}{2}}$; and (3) either $G_{{\displaystyle \frac{n}{2}},n}$ is a spanning subgraph of G and G is a spanning subgraph of $H_{{\displaystyle \frac{n}{2}},n}$ or $G_{{\displaystyle \frac{n}{2}},n}$ is a spanning subgraph of G and G is a spanning subgraph of $H_n$, where $k={\displaystyle \frac{n}{2}}$ for even $n\ge 6$. For the integers $n,k$ with $2\le k\le n-1$, the graph $G_{k,n}$ has the vertex set $V(G_{k,n})=\{x_1,x_2,\cdots ,x_n\}$ and the edge set $E(G_{k,n})=\{x_i{x}_{i+1}:i=1,2,\cdots ,n-k\}\cup \{x_{n-k+1}{x}_j:j=n-k+2,n-k+3,\cdots ,n\}$; the graph $H_{k,n}$ is obtained from $G_{k,n}$ by adding all the edges $x_i{x}_j$, where $n-k+2\le i<j\le n$; and for even $n\ge 6$ the graph $H_n$ is obtained from $G_{{\displaystyle \frac{n}{2}},n}$ by adding the edge $x_{{\displaystyle \frac{n}{2}}-1}{x}_{{\displaystyle \frac{n}{2}}+2}$ and all the edges $x_i{x}_j$, where ${\displaystyle \frac{n}{2}}+3\le i<j\le n$. This study provides the proof to complete the above theorem.

1. Introduction and Preliminaries

All graphs considered in this study are finite, simple, loopless, and unweighted. For a vertex x in a connected graph G, the status or transmission [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32] of x, denoted $s_G(x)$, is defined by $s_G(x)={\sum }_{y\in V(G)}{d}_G(x,y)$, where $d_G(x,y)$ is the distance between the vertices x and y in G. The concept of status was introduced by Harary in 1959 [13]. Slater [29] mentioned that the status of a vertex calculates the total transportation cost from this vertex to all other vertices in the graph. Vukičević and Caporossi [32] thought the status can be interpreted as a vertex’s contribution to a network’s communication cost. Let G be of order n and $\sigma (v)$ denote the average distance from a vertex v in G to all other vertices in G. That is, $\sigma (v)={\displaystyle \frac{s_G(v)}{n-1}}$. For complex network analysis, one major concern is centrality, which measures how central a vertex is in a network. Golbeck [33] mentioned that $\sigma (v)$ is used to measure the closeness centrality for vertices in a network. And Krnc and Škrekovski [15] studied the centralization of transmission in networks.

The minimum status or minimum transmission of G, denoted $ms(G)$, is defined by $ms(G)={min}_{x\in V(G)}{s}_G(x)$. The following theorem is about the upper bound on the minimum status of a connected graph with a fixed order and the graphs that attain the upper bound, which will be used in the main theorem later.

Theorem 1

(Proposition 2.1 in [34]). Let G be a connected graph of order $n\ge 3$. Then,

$ms(G)\le \left\{\begin{array}{cc}{\displaystyle \frac{n^2-1}{4}}\hfill & \mathit{if}n\mathit{is}\mathit{odd},\hfill \\ {\displaystyle \frac{n^2}{4}}\hfill & \mathit{if}n\mathit{is}\mathit{even}.\hfill \end{array}\right.$

The upper bound is attained if and only if G is either a path or a cycle.

Bounds on minimum status with several invariants of graphs are widely studied. Aouchiche and Hansen [34] gave a sharp lower bound on the minimum status of a graph with a fixed diameter and order. Lin et al. [18] obtained sharp lower and upper bounds on the minimum status of a graph with a fixed maximum degree and order. They characterized the extremal graphs for the lower bound and gave a necessary condition for graphs attaining the upper bound. Using another method, Rissner and Burkard [24] proved the same result for minimum status as in [18]. For graphs with a fixed matching number (or domination number) and order, Liang et al. [16] proposed a sharp upper bound on the minimum status and characterized the unique trees achieving the bound; they also determined the unique tree, so that its minimum status is as small as possible. Peng and Zhou [21] established sharp lower and upper bounds for the minimum status of trees with the following parameters: the diameter, the number of pendant vertices, the number of odd vertices, and the number of vertices of degree two, and characterized the extremal cases. Cheng et al. [7] determined the largest values for the minimum status of the series-reduced trees with the following fixed parameters: maximum degree, number of pendant vertices, diameter, matching number, and domination number, and characterized the unique extremal trees. For the aforementioned average distance $\sigma (v)$, the proximity of G is defined as ${min}_{v\in V(G)}\sigma (v)$, and the remoteness of G is defined as ${max}_{v\in V(G)}\sigma (v)$. It is seen that the proximity of G is equal to ${\displaystyle \frac{ms(G)}{n-1}}$. Similarly, the topic of bounds on proximity and remoteness with several invariants of graphs also attracts attention [1,8,9,25,34].

Lin et al. [18] provided a sharp lower bound and a sharp upper bound on the minimum status of connected graphs with a fixed maximum degree and order. Moreover, all graphs that attain the lower bound are obtained, and a necessary condition is determined for those that attain the upper bound. The following two types of graphs are needed to describe the result.

A rooted tree is a tree with a specific vertex designated as the root. Let T be a nontrivial rooted tree with root z. The height $h(T)$ of the tree T is defined by $h(T)={max}_{x\in V(T)}{d}_T(x,z)$, and the degree of a vertex x in T is denoted by $de{g}_T(x)$. For $h(T)\ge 2$ and $k\ge 2$, if $de{g}_T(x)=k$ whenever x is a vertex with $d_T(x,z)\le h(T)-2$, and $de{g}_T(x)\le k$ whenever x is a vertex with $d_T(x,z)=h(T)-1$, then T is called a balanced k-tree [18]. A balanced k-tree of order n is denoted by $B_{k,n}$. We note that $B_{k,n}$ may not be unique, but $ms(B_{k,n})$ is a fixed number for the given k and n. This value $ms(B_{k,n})$ is denoted by $b_{k,n}$. Next is another type of graph. For the integers $n,k$ with $n-1\ge k\ge 2$, let $G_{k,n}$ denote a graph with the vertex set $V(G_{k,n})=\{x_1,x_2,\cdots ,x_n\}$ and the edge set $E(G_{k,n})=\{x_i{x}_{i+1}:i=1,2,\cdots ,n-k\}\cup \{x_{n-k+1}{x}_j:j=n-k+2,n-k+3,\cdots ,n\}$. Figure 1 exhibits $G_{6,9}$ [18]. The graph $G_{k,n}$ is a tree and $de{g}_{G_{k,n}}(x_{n-k+1})=k$. Obviously, $G_{2,n}$ is a path and $G_{n-1,n}$ is a star. We call $G_{k,n}$ the k-grass of order n, or simply a grass, and use $g_{k,n}$ to denote the value $ms(G_{k,n})$.

The following theorem is provided by Lin et al. [18], which will be used in the main theorem.

Theorem 2

(Theorem 2.10 in [18]). Suppose that G is a connected graph of order n with $▵(G)=k$, where $k\ge 2$. Then, we have $b_{k,n}\le ms(G)\le g_{k,n}$. Furthermore, the lower bound is attained if and only if G contains some balanced k-tree $B_{k,n}$ as a spanning subgraph; if the upper bound is attained, then G contains the k-grass $G_{k,n}$ as a spanning subgraph.

For $k\le {\displaystyle \frac{n}{2}}$, Theorem 2.11 in [18] also proposes necessary and sufficient conditions for those graphs that attain the upper bound on the minimum status without proof. In recent decades, there have been various studies on the status, minimum status, or distance-related topics of graphs. The following research papers all cite [18]: [2,5,6,7,8,11,12,16,19,20,21,24,31]. However, this theorem is still without proof. Hence, our study aims to provide proof to complete this theorem.

To state the main theorem, we first illustrate two types of graphs which are defined in [18]. For integers k and n with $2\le k\le n-1$, let $H_{k,n}$ denote the graph obtained from the grass $G_{k,n}$ by adding all the edges $x_i{x}_j$, where $n-k+2\le i<j\le n$. For an even integer $n\ge 6$, let $H_n$ denote the graph obtained from the grass $G_{{\displaystyle \frac{n}{2}},n}$ by adding the edge $x_{{\displaystyle \frac{n}{2}}-1}{x}_{{\displaystyle \frac{n}{2}}+2}$ and all the edges $x_i{x}_j$, where ${\displaystyle \frac{n}{2}}+3\le i<j\le n$. Figure 2 exhibits $H_{5,10}$ and $H_{10}$.

Let $F,G$ and H be graphs. The graph G is said to be between F and H if F is a spanning subgraph of G and G is a spanning subgraph of H.

The main result of this study is as follows:

Theorem 3

(Theorem 2.11 in [18]). Let G be a connected graph of order n with $▵(G)=k$, where $2\le k\le {\displaystyle \frac{n}{2}}$. Then $ms(G)=g_{k,n}$ if and only if one of the following holds.

• (1) 

  G is a path or a cycle, where $k=2$.

• (2) 

  G is between $G_{k,n}$ and $H_{k,n}$, where $3\le k<{\displaystyle \frac{n}{2}}$.

• (3) 

  G is either between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$ or between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$, where $k={\displaystyle \frac{n}{2}}$ for even $n\ge 6$.

The detailed proof will be presented in the following section.

2. Proof of the Main Result

This section begins with several propositions, which will be used to prove lemmas. The main theorem follows directly from the lemmas.

The median of a graph G is the set: $\{x\in V(G):s_G(x)=ms(G)\}$. The following proposition is used to determine the median of a tree.

Proposition 1

([14,18]). Let T be a tree and x be a vertex of T. Then, x is in the median of T if and only if $|V(T^{\prime })|\le {\displaystyle \frac{1}{2}}\left|V(T)\right|$ holds for every component $T^{\prime }$ of $T-x$.

For a grass $G_{k,n}$, when we consider the case $2\le k\le {\displaystyle \frac{n}{2}}$, from Proposition 1 it is evident that the median of $G_{k,n}$ is the set $\{x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor +1}\}$ if n is odd and the set $\{x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor },x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor +1}\}$ if n is even.

Proposition 2.

Let H be a connected graph and G be a connected spanning subgraph of H. Let u be a vertex in the median of G. If there exists a vertex x in G with $xu\in E(H)$ and $xu\notin E(G)$, then $ms(H)<ms(G)$.

Proof. 

By assumption, $d_H(x,u)<d_G(x,u)$ and $d_H(v,u)\le d_G(v,u)$ for all $v\in V(G)-\{x\}$. Then $ms(H)\le s_H(u)<s_G(u)=ms(G)$. That is, $ms(H)<ms(G)$. □

Proposition 3.

Let $F,G$, and H be connected graphs. If G is between F and H and $ms(H)=ms(F)$, then $ms(G)=ms(F)$.

Proof. 

As $F\subseteq G\subseteq H$, we have $s_F(x)\ge s_G(x)\ge s_H(x)$ for all $x\in V(G)$. Then, $ms(F)\ge ms(G)\ge ms(H)$. As $ms(H)=ms(F)$, we have $ms(G)=ms(F)$. □

The following propositions are trivial. We omit the proofs.

Proposition 4.

Let G be a connected graph. If $x,y\in V(G)$, $xy\in E(G)$, and $|\{v\in V(G):d_G(v,x)<d_G(v,y)\}| < |\{v\in V(G):d_G(v,y)<d_G(v,x)\}|$, then $s_G(y)<s_G(x)$.

Proposition 5.

Let C be the only cycle in a connected graph G. Then ${\sum }_{v\in V(C)}{d}_G(v,p)={\sum }_{v\in V(C)}{d}_G(v,q)$ for any two vertices $p,q\in V(C)$.

Next are the lemmas for the main theorem.

Lemma 1.

Let G be a connected graph of order $n\ge 3$. Then $ms(G)=g_{2,n}$ if and only if G is a path or a cycle.

Proof. 

According to Theorem 1, it suffices to show that

$g_{2,n}=\left\{\begin{array}{cc}{\displaystyle \frac{n^2-1}{4}}\hfill & \mathrm{if}n\mathrm{is}\mathrm{odd},\hfill \\ {\displaystyle \frac{n^2}{4}}\hfill & \mathrm{if}n\mathrm{is}\mathrm{even}.\hfill \end{array}\right.$

Here, $g_{2,n}=ms(G_{2,n})$, and the grass $G_{2,n}$ is in fact a path $P:x_1{x}_2\cdots x_n$. By Proposition 1,

$\begin{array}{ccc}\hfill g_{2,n}& =& s_{G_{2,n}}(x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor +1})\hfill \\ & =& \left\{\begin{array}{cc}2(1+2+\cdots +\lfloor {\displaystyle \frac{n}{2}}\rfloor )\hfill & \mathrm{if}n\mathrm{is}\mathrm{odd},\hfill \\ (1+2+\cdots +\lfloor {\displaystyle \frac{n}{2}}\rfloor )+(1+2+\cdots +(\lfloor {\displaystyle \frac{n}{2}}\rfloor -1))\hfill & \mathrm{if}n\mathrm{is}\mathrm{even}.\hfill \end{array}\right.\hfill \\ & =& \left\{\begin{array}{cc}{\lfloor {\displaystyle \frac{n}{2}}\rfloor }^2+\lfloor {\displaystyle \frac{n}{2}}\rfloor \hfill & \mathrm{if}n\mathrm{is}\mathrm{odd},\hfill \\ {\lfloor {\displaystyle \frac{n}{2}}\rfloor }^2\hfill & \mathrm{if}n\mathrm{is}\mathrm{even}.\hfill \end{array}\right.\hfill \\ & =& \left\{\begin{array}{cc}{\displaystyle \frac{n^2-1}{4}}\hfill & \mathrm{if}n\mathrm{is}\mathrm{odd},\hfill \\ {\displaystyle \frac{n^2}{4}}\hfill & \mathrm{if}n\mathrm{is}\mathrm{even}.\hfill \end{array}\right.\hfill \end{array}$

 □

Lemma 2.

Let G be a connected graph of order n with $▵(G)=k$, where $3\le k\le {\displaystyle \frac{n}{2}}$. Then $ms(G)=g_{k,n}$ if and only if one of the following holds.

• (1) 

  G is between $G_{k,n}$ and $H_{k,n}$, where $3\le k<{\displaystyle \frac{n}{2}}$.

• (2) 

  G is either between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$ or between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$, where $k={\displaystyle \frac{n}{2}}$ for even $n\ge 6$.

Proof. 

We first prove the sufficiency.

• (1) 

  Let G be between $G_{k,n}$ and $H_{k,n}$, where $3\le k<{\displaystyle \frac{n}{2}}$. We note that any graph between $G_{k,n}$ and $H_{k,n}$ has the maximum degree k and the order n. From Proposition 3, it suffices to show that $ms(H_{k,n})=ms(G_{k,n})$. It is evident that $s_{H_{k,n}}(x_i)=s_{G_{k,n}}(x_i)$ for $1\le i\le n-k+1$. By Proposition 4, $s_{H_{k,n}}(x_i)>s_{H_{k,n}}(x_{n-k+1})$ for $n-k+2\le i\le n$. As $ms(G_{k,n})=s_{G_{k,n}}(x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor +1})$, where $\lfloor {\displaystyle \frac{n}{2}}\rfloor +1<n-k+1$, we have $ms(H_{k,n})=s_{H_{k,n}}(x_{\lfloor {\displaystyle \frac{n}{2}}\rfloor +1})$. That is, $ms(H_{k,n})=ms(G_{k,n})$.

• (2) 

  We note that any graph between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$, or between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$, has the maximum degree $k={\displaystyle \frac{n}{2}}$ and the order n, where n is even and $n\ge 6$. First, let G be between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$, the proof is the same as in (1) except that we have $\lfloor {\displaystyle \frac{n}{2}}\rfloor +1=n-k+1$ in this case. Next, let G be between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$. By Proposition 3, it suffices to show that $ms(H_n)=ms(G_{{\displaystyle \frac{n}{2}},n})$. By applying Proposition 4, we can see that

  $s_{H_n}(x_{{\displaystyle \frac{n}{2}}-1})=s_{H_n}(x_{{\displaystyle \frac{n}{2}}})=s_{H_n}(x_{{\displaystyle \frac{n}{2}}+1})=s_{H_n}(x_{{\displaystyle \frac{n}{2}}+2}),$

  $s_{H_n}(x_{{\displaystyle \frac{n}{2}}-1})<s_{H_n}(x_{{\displaystyle \frac{n}{2}}-2})<\cdots <s_{H_n}(x_1),\mathrm{and}$

  $s_{H_n}(x_{{\displaystyle \frac{n}{2}}+1})<s_{H_n}(v)\mathrm{for}\mathrm{all}v\in \{x_{{\displaystyle \frac{n}{2}}+3},x_{{\displaystyle \frac{n}{2}}+4},\cdots ,x_n\}.$

  Thus, $ms(H_n)=s_{H_n}(x_{{\displaystyle \frac{n}{2}}+1})$. Since $ms(G_{{\displaystyle \frac{n}{2}},n})=s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}+1})$ and clearly $s_{H_n}(x_{{\displaystyle \frac{n}{2}}+1})$$=s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}+1})$, we have $ms(H_n)=ms(G_{{\displaystyle \frac{n}{2}},n})$.

Next, we prove the necessity. Assume that $ms(G)=g_{k,n}$, where $▵(G)=k$ and $3\le k\le {\displaystyle \frac{n}{2}}$. By Theorem 2, G contains $G_{k,n}$ as a spanning subgraph. Distinguish between the following two cases. Case 1: $3\le k<{\displaystyle \frac{n}{2}}$, and Case 2: $3\le k={\displaystyle \frac{n}{2}}$.

• Case 1:

  $3\le k<{\displaystyle \frac{n}{2}}$. We claim that $E(G)-E(H_{k,n})=\varnothing$, and this implies that G is between $G_{k,n}$ and $H_{k,n}$. Suppose, to the contrary, that there exists an edge $x_i{x}_j\in E(G)-E(H_{k,n})$, where $1\le i<j\le n$. As $x_i{x}_j\notin E(H_{k,n})$, we note that there is at most one of the two numbers i and j that is in $\{n-k+1,n-k+2,\cdots ,n\}$. Let $G^{\prime }=G_{k,n}+x_i{x}_j$ and C be a cycle in $G^{\prime }$. It is clear that $G^{\prime }\subseteq G$ and then $ms(G)\le ms(G^{\prime })$, and C is the only cycle in $G^{\prime }$. Distinguish two subcases. Case 1.1: n is even, and Case 1.2: n is odd.

• Case 1.1:

  n is even. In this case, the median of $G_{k,n}$ is $\{x_{{\displaystyle \frac{n}{2}}},x_{{\displaystyle \frac{n}{2}}+1}\}$, where ${\displaystyle \frac{n}{2}}+1<n-k+1$. As $G_{k,n}$ is a spanning subgraph of $G^{\prime }$, if $i\in \{{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1\}$ or $j\in \{{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1\}$, then by Proposition 2, we see that $ms(G^{\prime })<ms(G_{k,n})=g_{k,n}$. Then, $ms(G)<g_{k,n}$. Which contradicts the assumption that $ms(G)=g_{k,n}$. Therefore, we have $i,j\notin \{{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1\}$. Without loss of generality, we distinguish two cases: (i) $1\le i<j\le {\displaystyle \frac{n}{2}}-1$ or ${\displaystyle \frac{n}{2}}+2\le i<j\le n-k+2$, and (ii) $1\le i\le {\displaystyle \frac{n}{2}}-1$ and ${\displaystyle \frac{n}{2}}+2\le j\le n-k+2$.

• (i) 

  $1\le i<j\le {\displaystyle \frac{n}{2}}-1$ or ${\displaystyle \frac{n}{2}}+2\le i<j\le n-k+2$. First, we consider the case $1\le i<j\le {\displaystyle \frac{n}{2}}-1$. As $d_{G^{\prime }}(x_i,x_{{\displaystyle \frac{n}{2}}})<d_{G_{k,n}}(x_i,x_{{\displaystyle \frac{n}{2}}})$ and $d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}})\le d_{G_{k,n}}(x_t,x_{{\displaystyle \frac{n}{2}}})$ for $t\ne i$, we have $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{k,n}}(x_{{\displaystyle \frac{n}{2}}})$. This implies that $ms(G^{\prime })\le s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{k,n}}(x_{{\displaystyle \frac{n}{2}}})=g_{k,n}$. Then, $ms(G)<g_{k,n}$, which is a contradiction. Next is the case ${\displaystyle \frac{n}{2}}+2\le i<j\le n-k+2$. Similarly, $d_{G^{\prime }}(x_j,x_{{\displaystyle \frac{n}{2}}})<d_{G_{k,n}}(x_j,x_{{\displaystyle \frac{n}{2}}})$ and $d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}})\le d_{G_{k,n}}(x_t,x_{{\displaystyle \frac{n}{2}}})$ for $t\ne j$, we have $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{k,n}}(x_{{\displaystyle \frac{n}{2}}})$. And then, $ms(G)\le ms(G^{\prime })\le s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{k,n}}(x_{{\displaystyle \frac{n}{2}}})=g_{k,n}$, which is a contradiction.

• (ii) 

  $1\le i\le {\displaystyle \frac{n}{2}}-1$ and ${\displaystyle \frac{n}{2}}+2\le j\le n-k+2$. First, we see that $d_{G^{\prime }}(v,x_j)\le d_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})$ for $v\in \{x_1,x_2,\cdots ,x_{i-1}\}$. Next, by Proposition 5, ${\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_j)$$={\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})$, as $x_j,x_{{\displaystyle \frac{n}{2}}}\in V(C)$, where C is the aforementioned only cycle of $G^{\prime }$. And $d_{G^{\prime }}(v,x_j)<d_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})$ for $v\in V(G^{\prime })-\{x_1,x_2,\cdots ,x_{i-1}\}-V(C)=\{x_{j+1},x_{j+2},\cdots ,x_n\}$. Note that $\{x_1,x_2,\cdots ,x_{i-1}\}=\varnothing$ if $i=1$.

  Then

  $\begin{array}{ccc}\hfill ms(G)& \le & ms(G^{\prime })\hfill \\ & \le & s_{G^{\prime }}(x_j)\hfill \\ & =& \sum _{v\in V(G^{\prime })}{d}_{G^{\prime }}(v,x_j)\hfill \\ & =& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_j)+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_j)+\sum _{v\in \{x_{j+1},x_{j+2},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_j)\hfill \\ & <& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})+\sum _{v\in \{x_{j+1},x_{j+2},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})\hfill \\ & =& \sum _{v\in V(G^{\prime })}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n}{2}}})\hfill \\ & =& s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})\hfill \\ & \le & s_{G_{k,n}}(x_{{\displaystyle \frac{n}{2}}})\hfill \\ & =& g_{k,n}.\hfill \end{array}$

  Thus, $ms(G)<g_{k,n}$, which is a contradiction.

• Case 1.2:

  n is odd. In this case, the median of $G_{k,n}$ is $\{x_{{\displaystyle \frac{n+1}{2}}}\}$, where ${\displaystyle \frac{n+1}{2}}<n-k+1$. As $G_{k,n}$ is a spanning subgraph of $G^{\prime }$, by Proposition 2, if $i={\displaystyle \frac{n+1}{2}}$ or $j={\displaystyle \frac{n+1}{2}}$, then $ms(G)\le ms(G^{\prime })<ms(G_{k,n})=g_{k,n}$, which is a contradiction. Thus, we have $i,j\ne {\displaystyle \frac{n+1}{2}}$. Recall that $x_i{x}_j\notin E(H_{k,n})$, hence there is at most one of the two numbers i and j that is in $\{n-k+1,n-k+2,\cdots ,n\}$. Without loss of generality, we distinguish three cases: (i) $1\le i<j\le {\displaystyle \frac{n-1}{2}}$ or ${\displaystyle \frac{n+3}{2}}\le i<j\le n-k+2$, (ii) $1\le i<{\displaystyle \frac{n+1}{2}}<j\le n-k+1$, and (iii) $1\le i<{\displaystyle \frac{n+1}{2}}$ and $j=n-k+2$.

• (i) 

  $1\le i<j\le {\displaystyle \frac{n-1}{2}}$ or ${\displaystyle \frac{n+3}{2}}\le i<j\le n-k+2$. The arguments are similar to those presented in Case 1.1(i).

• (ii) 

  $1\le i<{\displaystyle \frac{n+1}{2}}<j\le n-k+1$. In this case, $d_{G^{\prime }}(v,x_j)\le d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in \{x_1,x_2,\cdots ,x_{i-1}\}$. By Proposition 5, ${\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_j)={\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$, as $x_j,x_{{\displaystyle \frac{n+1}{2}}}$$\in V(C)$. And $d_{G^{\prime }}(v,x_j)<d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in V(G^{\prime })-\{x_1,x_2,\cdots ,$$x_{i-1}\}-V(C)=\{x_{j+1},x_{j+2},\cdots ,x_n\}$.

  Then

  $\begin{array}{ccc}\hfill ms(G)& \le & ms(G^{\prime })\hfill \\ & \le & s_{G^{\prime }}(x_j)\hfill \\ & =& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_j)+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_j)+\sum _{v\in \{x_{j+1},x_{j+2},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_j)\hfill \\ & <& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in \{x_{j+1},x_{j+2},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& s_{G^{\prime }}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & \le & s_{G_{k,n}}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& g_{k,n}.\hfill \end{array}$

  Thus, $ms(G)<g_{k,n}$, which is a contradiction.

• (iii) 

  $1\le i<{\displaystyle \frac{n+1}{2}}$ and $j=n-k+2$. For $k<{\displaystyle \frac{n}{2}}$ and n is odd, we have $k\le {\displaystyle \frac{n-1}{2}}$. Then, ${\displaystyle \frac{n+1}{2}}\le n-k$. Now, consider the three cases: (a) ${\displaystyle \frac{n+1}{2}}=n-k$, $i={\displaystyle \frac{n-1}{2}}$, (b) ${\displaystyle \frac{n+1}{2}}=n-k$, $1\le i<{\displaystyle \frac{n-1}{2}}$, and (c) ${\displaystyle \frac{n+1}{2}}<n-k$.

• (a) 

  ${\displaystyle \frac{n+1}{2}}=n-k$, $i={\displaystyle \frac{n-1}{2}}$. In this case, the vertex $x_i=x_{{\displaystyle \frac{n-1}{2}}}$ is adjacent to $x_{n-k}=x_{{\displaystyle \frac{n+1}{2}}}$, and $x_{n-k+1}=x_{{\displaystyle \frac{n+1}{2}}+1}$ is the vertex of degree k in $G^{\prime }$. We see that

  $|\{v\in V(G^{\prime }):d_{G^{\prime }}(v,x_i)<d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})\}| = |\{x_1,x_2,\cdots ,x_{i-1},x_{n-k+2}\}| = i={\displaystyle \frac{n-1}{2}}$, and

  $|\{v\in V(G^{\prime }):d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})<d_{G^{\prime }}(v,x_i)\}| = |\{x_{n-k+1}\}\bigcup \{x_{n-k+3},x_{n-k+4}\cdots ,x_n\}| = k-1.$

  As $k=n-{\displaystyle \frac{n+1}{2}}={\displaystyle \frac{n-1}{2}}$, we have $k-1<{\displaystyle \frac{n-1}{2}}$, by Proposition 4, $s_{G^{\prime }}(x_i)<s_{G^{\prime }}(x_{{\displaystyle \frac{n+1}{2}}})$. Then $ms(G)\le ms(G^{\prime })\le s_{G^{\prime }}(x_i)<s_{G^{\prime }}(x_{{\displaystyle \frac{n+1}{2}}})\le s_{G_{k,n}}(x_{{\displaystyle \frac{n+1}{2}}})=g_{k,n}$, that is, $ms(G)<g_{k,n}$, which is a contradiction.

• (b) 

  ${\displaystyle \frac{n+1}{2}}=n-k$, $1\le i<{\displaystyle \frac{n-1}{2}}$. In this case, $d_{G^{\prime }}(v,x_{n-k+1})\le d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in \{x_1,x_2,\cdots ,x_{i-1}\}$. Recall that C is the only cycle in $G^{\prime }$. By Proposition 5,

  ${\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{n-k+1})={\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$, as $x_{n-k+1},x_{{\displaystyle \frac{n+1}{2}}}\in V(C)$. And $d_{G^{\prime }}(v,x_{n-k+1})$$<d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in V(G^{\prime })-\{x_1,x_2,\cdots ,x_{i-1}\}-V(C)=\{x_{n-k+3},x_{n-k+4},\cdots ,x_n\}$.

  Then

  $\begin{array}{ccc}\hfill ms(G)& \le & ms(G^{\prime })\hfill \\ & \le & s_{G^{\prime }}(x_{n-k+1})\hfill \\ & =& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{n-k+1})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{n-k+1})+\sum _{v\in \{x_{n-k+3},x_{n-k+4},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{n-k+1})\hfill \\ & <& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in \{x_{n-k+3},x_{n-k+4},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& s_{G^{\prime }}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & \le & s_{G_{k,n}}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& g_{k,n}.\hfill \end{array}$

  Thus, $ms(G)<g_{k,n}$, which is a contradiction.

• (c) 

  ${\displaystyle \frac{n+1}{2}}<n-k$. In this case, $d_{G^{\prime }}(v,x_{n-k+2})\le d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in \{x_1,x_2,\cdots ,x_{i-1}\}$. By Proposition 5, ${\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{n-k+2})={\sum }_{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$, as $x_{n-k+2},x_{{\displaystyle \frac{n+1}{2}}}$$\in V(C)$. And $d_{G^{\prime }}(v,x_{n-k+2})<d_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})$ for $v\in V(G^{\prime })-\{x_1,x_2,\cdots ,x_{i-1}\}-V(C)=\{x_{n-k+3},$$x_{n-k+4},\cdots ,x_n\}$.

  Then

  $\begin{array}{ccc}\hfill ms(G)& \le & ms(G^{\prime })\hfill \\ & \le & s_{G^{\prime }}(x_{n-k+2})\hfill \\ & =& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{n-k+2})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{n-k+2})+\sum _{v\in \{x_{n-k+3},x_{n-k+4},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{n-k+2})\hfill \\ & <& \sum _{v\in \{x_1,x_2,\cdots ,x_{i-1}\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in V(C)}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})+\sum _{v\in \{x_{n-k+3},x_{n-k+4},\cdots ,x_n\}}{d}_{G^{\prime }}(v,x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& s_{G^{\prime }}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & \le & s_{G_{k,n}}(x_{{\displaystyle \frac{n+1}{2}}})\hfill \\ & =& g_{k,n}.\hfill \end{array}$

  Thus, $ms(G)<g_{k,n}$, which is a contradiction.

From the above contradictions, we see that $E(G)-E(H_{k,n})=\varnothing$. That is, G is between $G_{k,n}$ and $H_{k,n}$.

• Case 2:

  $3\le k={\displaystyle \frac{n}{2}}$. In this case, the median of $G_{{\displaystyle \frac{n}{2}},n}$ is $\{x_{{\displaystyle \frac{n}{2}}},x_{{\displaystyle \frac{n}{2}}+1}\}$. Distinguish between the following two subcases. Case 2.1: $x_{{\displaystyle \frac{n}{2}}-1}{x}_t\in E(G)$ for some $t\in \{{\displaystyle \frac{n}{2}}+2,{\displaystyle \frac{n}{2}}+3,\cdots ,n\}$, and Case 2.2: $x_{{\displaystyle \frac{n}{2}}-1}{x}_t\notin E(G)$ for all $t\in \{{\displaystyle \frac{n}{2}}+2,{\displaystyle \frac{n}{2}}+3,\cdots ,n\}$.

• Case 2.1:

  $x_{{\displaystyle \frac{n}{2}}-1}{x}_t\in E(G)$ for some $t\in \{{\displaystyle \frac{n}{2}}+2,{\displaystyle \frac{n}{2}}+3,\cdots ,n\}$. In this case we show that G is between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$. Without loss of generality, it is assumed that $x_{{\displaystyle \frac{n}{2}}-1}{x}_{{\displaystyle \frac{n}{2}}+2}\in E(G)$. We claim that $E(G)-E(H_n)=\varnothing$, and this implies that G is between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$. On the contrary, suppose that there exists an edge $x_i{x}_j\in E(G)-E(H_n)$, where $1\le i<j\le n$. Let $G^{\prime }=G_{{\displaystyle \frac{n}{2}},n}+x_{{\displaystyle \frac{n}{2}}-1}{x}_{{\displaystyle \frac{n}{2}}+2}$ and $G^{\prime \prime }=G^{\prime }+x_i{x}_j$. By Proposition 4, it is evident that $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}-1})=s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})=s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})=s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+2})=ms(G^{\prime })$. And since $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})=g_{{\displaystyle \frac{n}{2}},n}$, we have $ms(G^{\prime })=g_{{\displaystyle \frac{n}{2}},n}$. As $G^{\prime }$ is a spanning subgraph of $G^{\prime \prime }$, and the median of $G^{\prime }$ is $\{x_{{\displaystyle \frac{n}{2}}-1},x_{{\displaystyle \frac{n}{2}}},x_{{\displaystyle \frac{n}{2}}+1},x_{{\displaystyle \frac{n}{2}}+2}\}$, by Proposition 2, if i or j is in $\{{\displaystyle \frac{n}{2}}-1,{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1,{\displaystyle \frac{n}{2}}+2\}$, then $ms(G)\le ms(G^{\prime \prime })<ms(G^{\prime })=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction. Therefore, we have $i,j\notin \{{\displaystyle \frac{n}{2}}-1,{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1,{\displaystyle \frac{n}{2}}+2\}$. Distinguish the following two cases. (i) $1\le i<j\le {\displaystyle \frac{n}{2}}-2$, and (ii) $1\le i\le {\displaystyle \frac{n}{2}}-2,{\displaystyle \frac{n}{2}}+3\le j\le n$.

• (i) 

  $1\le i<j\le {\displaystyle \frac{n}{2}}-2$. As $d_{G^{\prime \prime }}(x_i,x_{{\displaystyle \frac{n}{2}}-1})<d_{G^{\prime }}(x_i,x_{{\displaystyle \frac{n}{2}}-1})$, and $d_{G^{\prime \prime }}(x_t,x_{{\displaystyle \frac{n}{2}}-1})\le d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}-1})$ for all $t\ne i$, we have $s_{G^{\prime \prime }}(x_{{\displaystyle \frac{n}{2}}-1})<s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}-1})$. Thus, $ms(G)\le ms(G^{\prime \prime })\le s_{G^{\prime \prime }}(x_{{\displaystyle \frac{n}{2}}-1})<s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}-1})=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction.

• (ii) 

  $1\le i\le {\displaystyle \frac{n}{2}}-2,{\displaystyle \frac{n}{2}}+3\le j\le n$. In this case, $d_{G^{\prime \prime }}(x_i,x_{{\displaystyle \frac{n}{2}}+1})<d_{G^{\prime }}(x_i,x_{{\displaystyle \frac{n}{2}}+1})$, and $d_{G^{\prime \prime }}(x_t,x_{{\displaystyle \frac{n}{2}}+1})\le d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}+1})$ for all $t\ne i$, we have $s_{G^{\prime \prime }}(x_{{\displaystyle \frac{n}{2}}+1})<s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})$. Thus, $ms(G)\le ms(G^{\prime \prime })\le s_{G^{\prime \prime }}(x_{{\displaystyle \frac{n}{2}}+1})<s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction.

  Thus, $E(G)-E(H_n)=\varnothing$ and G is between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_n$.

• Case 2.2:

  $x_{{\displaystyle \frac{n}{2}}-1}{x}_t\notin E(G)$ for all $t\in \{{\displaystyle \frac{n}{2}}+2,{\displaystyle \frac{n}{2}}+3,\cdots ,n\}$. In this case we show that G is between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$. It suffices to show that $E(G)-E(H_{{\displaystyle \frac{n}{2}},n})=\varnothing$ holds. On the contrary, suppose that there exists an edge $x_i{x}_j\in E(G)-E(H_{{\displaystyle \frac{n}{2}},n})$. Let $G^{\prime }=G_{{\displaystyle \frac{n}{2}},n}+x_i{x}_j$. The median of $G_{{\displaystyle \frac{n}{2}},n}$ is $\{x_{{\displaystyle \frac{n}{2}}},x_{{\displaystyle \frac{n}{2}}+1}\}$, we have $i,j\notin \{{\displaystyle \frac{n}{2}},{\displaystyle \frac{n}{2}}+1\}$. As if this is not true, by Proposition 2, we have $ms(G)\le ms(G^{\prime })<ms(G_{{\displaystyle \frac{n}{2}},n})=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction. Distinguish the following two cases. (i) $1\le i<j\le {\displaystyle \frac{n}{2}}-1$, and (ii) $1\le i\le {\displaystyle \frac{n}{2}}-2,{\displaystyle \frac{n}{2}}+2\le j\le n$.

• (i) 

  $1\le i<j\le {\displaystyle \frac{n}{2}}-1$. As $d_{G^{\prime }}(x_i,x_{{\displaystyle \frac{n}{2}}})<d_{G_{{\displaystyle \frac{n}{2}},n}}(x_i,x_{{\displaystyle \frac{n}{2}}})$, and $d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}})\le d_{G_{{\displaystyle \frac{n}{2}},n}}(x_t,x_{{\displaystyle \frac{n}{2}}})$ for all $t\ne i$, we have $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}})$. Thus, $ms(G)\le ms(G^{\prime })\le s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}})<s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}})=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction.

• (ii) 

  $1\le i\le {\displaystyle \frac{n}{2}}-2,{\displaystyle \frac{n}{2}}+2\le j\le n$. In this case, $d_{G^{\prime }}(x_i,x_{{\displaystyle \frac{n}{2}}+1})<d_{G_{{\displaystyle \frac{n}{2}},n}}(x_i,x_{{\displaystyle \frac{n}{2}}+1})$, and $d_{G^{\prime }}(x_t,x_{{\displaystyle \frac{n}{2}}+1})\le d_{G_{{\displaystyle \frac{n}{2}},n}}(x_t,x_{{\displaystyle \frac{n}{2}}+1})$ for all $t\ne i$, we have $s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})<s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}+1})$. Thus, $ms(G)\le ms(G^{\prime })\le s_{G^{\prime }}(x_{{\displaystyle \frac{n}{2}}+1})<s_{G_{{\displaystyle \frac{n}{2}},n}}(x_{{\displaystyle \frac{n}{2}}+1})=g_{{\displaystyle \frac{n}{2}},n}$, which is a contradiction.

Thus, $E(G)-E(H_{{\displaystyle \frac{n}{2}},n})=\varnothing$ and G is between $G_{{\displaystyle \frac{n}{2}},n}$ and $H_{{\displaystyle \frac{n}{2}},n}$.

We see that the necessity holds. □

Theorem 3, the main result of this study, follows from Lemmas 1 and 2.

The graph H in Figure 3 has order 10 and $▵(H)=5$. It is easily seen that $s_H(x_6)=g_{5,10}$. Since it is neither between $G_{5,10}$ and $H_{5,10}$ nor between $G_{5,10}$ and $H_{10}$, by applying Theorem 3, we have $ms(H)<g_{5,10}$. By Proposition 4, we can see that $s_H(x_7)<s_H(x_6)$.

We conclude this study with the following future work: For connected graphs of order n with maximum degree k where ${\displaystyle \frac{n}{2}}<k$, find the necessary and sufficient conditions for attaining the upper bound $g_{k,n}$ on minimum status.

Author Contributions

Conceptualization, W.-H.T. and C.L.; Methodology, W.-H.T. and C.L.; Validation, J.-L.S.; Investigation, W.-H.T., J.-L.S. and C.L.; Writing—original draft, W.-H.T. and C.L.; Writing—review and editing, J.-L.S.; Funding acquisition, J.-L.S. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data is contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures

Figure 1. Grass [Forumla omitted. See PDF.].

Figure 2. Examples of [Forumla omitted. See PDF.] and [Forumla omitted. See PDF.] for [Forumla omitted. See PDF.] and [Forumla omitted. See PDF.].

Figure 3. Graph H of order 10 and [Forumla omitted. See PDF.] with [Forumla omitted. See PDF.].

References

1. Aouchiche, M.; Hansen, P. Proximity, remoteness and girth in graphs. Discret. Appl. Math.; 2017; 222, pp. 31-39. [DOI: https://dx.doi.org/10.1016/j.dam.2017.01.025]

2. Abiad, A.; Brimkov, B.; Grigoriev, A. On the status sequences of trees. Theoret. Comput. Sci.; 2021; 856, pp. 110-120. [DOI: https://dx.doi.org/10.1016/j.tcs.2020.12.030]

3. Buckley, F.; Harary, F. Distance in Graphs; Addison-Wesley Publishing Company: Boston, MA, USA, 1990.

4. Buckley, F.; Harary, F. Unsolved problems on distance in graphs. Electron. Notes Discret. Math.; 2002; 11, pp. 89-97. [DOI: https://dx.doi.org/10.1016/S1571-0653(04)00057-5]

5. Bielak, H.; Powroźnik, K. Statuses and double branch weights of quadrangular outerplanar graphs. Ann. Univ. Mariae Curie-Skłodowska Sect. A; 2015; 69, pp. 5-21.

6. Cheng, M.; Zhou, B. Minimum and maximum resistance status of unicyclic graphs. J. Math. Res. Appl.; 2022; 42, pp. 463-475.

7. Cheng, M.; Lin, H.; Zhou, B. Minimum status of series-reduced trees with given parameters. Bull. Braz. Math. Soc.; 2022; 53, pp. 701-720. [DOI: https://dx.doi.org/10.1007/s00574-021-00278-1]

8. Dankelmann, P.; Mafunda, S. On the difference between proximity and other distance parameters in triangle-free graphs and C₄-free graphs. Discret. Appl. Math.; 2022; 321, pp. 295-307. [DOI: https://dx.doi.org/10.1016/j.dam.2022.06.037]

9. Dankelmann, P. Proximity, remoteness and minimum degree. Discret. Appl. Math.; 2015; 184, pp. 223-228. [DOI: https://dx.doi.org/10.1016/j.dam.2014.11.012]

10. Entringer, R.C.; Jackson, D.E.; Snyder, D.A. Distance in graphs. Czechoslov. Math. J.; 1976; 26, pp. 283-296. [DOI: https://dx.doi.org/10.21136/CMJ.1976.101401]

11. Guo, H.; Zhou, B. On extremal leaf status and internal status. RAIRO Oper. Res.; 2022; 56, pp. 415-430. [DOI: https://dx.doi.org/10.1051/ro/2022010]

12. Guo, H.; Zhou, B. Minimum status of trees with a given degree sequence. Acta Inform.; 2023; 60, pp. 1-10. [DOI: https://dx.doi.org/10.1007/s00236-022-00416-2]

13. Harary, F. Status and contrastatus. Sociometry; 1959; 22, pp. 23-43. [DOI: https://dx.doi.org/10.2307/2785610]

14. Kang, A.; Ault, D. Some properties of a centroid of a free tree. Inf. Process. Lett.; 1975; 4, pp. 18-20. [DOI: https://dx.doi.org/10.1016/0020-0190(75)90055-1]

15. Krnc, M.; Škrekovski, R. Centralization of transmission in networks. Discret. Math.; 2015; 338, pp. 2412-2420. [DOI: https://dx.doi.org/10.1016/j.disc.2015.06.011]

16. Liang, C.; Zhou, B.; Guo, H. Minimum status, matching and domination of graphs. Comput. J.; 2021; 64, pp. 1384-1392. [DOI: https://dx.doi.org/10.1093/comjnl/bxaa057]

17. Lin, C.; Shang, J.-L. Statuses and branch-weights of weighted trees. Czechoslov. Math. J.; 2009; 59, pp. 1019-1025. [DOI: https://dx.doi.org/10.1007/s10587-009-0071-x]

18. Lin, C.; Tsai, W.-H.; Shang, J.-L.; Zhang, Y.-J. Minimum statuses of connected graphs with fixed maximum degree and order. J. Comb. Optim.; 2012; 24, pp. 147-161. [DOI: https://dx.doi.org/10.1007/s10878-011-9412-4]

19. Lin, C.; Tsai, W.-H.; Shang, J.-L.; Lee, M.-J. Maximum variances and minimum statuses of connected weighted graphs. Util. Math.; 2017; 104, pp. 277-293.

20. Lin, H.; Zhou, B. Which numbers are status differences?. Appl. Math. Comput.; 2021; 399, 126004. [DOI: https://dx.doi.org/10.1016/j.amc.2021.126004]

21. Peng, Z.; Zhou, B. Minimum status of trees with given parameters. RAIRO Oper. Res.; 2021; 55, pp. S765-S785. [DOI: https://dx.doi.org/10.1051/ro/2020015]

22. Pachter, L. Constructing status injective graphs. Discret. Appl. Math.; 1997; 80, pp. 107-113. [DOI: https://dx.doi.org/10.1016/S0166-218X(97)00073-5]

23. Qiao, P.; Zhan, X. Pairs of a tree and a nontree graph with the same status sequence. Discret. Math.; 2020; 343, 111662. [DOI: https://dx.doi.org/10.1016/j.disc.2019.111662]

24. Rissner, R.; Burkard, R.E. Bounds on the radius and status of graphs. Networks; 2014; 64, pp. 76-83. [DOI: https://dx.doi.org/10.1002/net.21558]

25. Sedlar, J. Remoteness, proximity and few other distance invariants in graphs. Filomat; 2013; 27, pp. 1425-1435. [DOI: https://dx.doi.org/10.2298/FIL1308425S]

26. Shang, J.-L.; Lin, C. Spiders are status unique in trees. Discret. Math.; 2011; 311, pp. 785-791. [DOI: https://dx.doi.org/10.1016/j.disc.2011.01.020]

27. Shang, J.-L. On constructing graphs with the same status sequence. Ars Combin.; 2014; 113, pp. 429-433.

28. Shang, J.-L.; Shyu, T.-W.; Lin, C. Weakly status injective trees are status unique in trees. Ars Combin.; 2018; 139, pp. 133-143.

29. Slater, P.J. Maximin facility location. J. Res. Natl. Bur. Stand. B Math. Sci.; 1975; 79B, pp. 107-115. [DOI: https://dx.doi.org/10.6028/jres.079B.011]

30. Slater, P.J. Counterexamples to Randić’s conjecture on distance degree sequences for trees. J. Graph Theory; 1982; 6, pp. 89-92. [DOI: https://dx.doi.org/10.1002/jgt.3190060111]

31. Subhamathi, A.R.; Changat, M. Upperbound for maximum remoteness in arbitrary graph. Int. J. Pure Appl. Math.; 2015; 101, pp. 719-727.

32. Vukičević, D.; Caporossi, G. Network descriptors based on betweenness centrality and transmission and their extremal values. Discret. Appl. Math.; 2013; 161, pp. 2678-2686. [DOI: https://dx.doi.org/10.1016/j.dam.2013.04.005]

33. Golbeck, J. Analyzing the Social Web; Morgan Kaufmann: Burlington, MA, USA, 2013.

34. Aouchiche, M.; Hansen, P. Proximity and remoteness in graphs: Results and conjectures. Networks; 2011; 58, pp. 95-102. [DOI: https://dx.doi.org/10.1002/net.20450]