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

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 <= k <= 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 Delta(G) = k, where 2 <= k <= 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,H-n, where 3 <= k < n/2; and (3) either G(n/2,)n is a spanning subgraph of G and G is a spanning subgraph of H(n/2,)n or G(n/2,n) is a spanning subgraph of G and G is a spanning subgraph of H-n, where k = n/2 for even n >= 6. For the integers n,k with 2 <= k <= n-1, the graph G(k,n) has the vertex set V(G(k,n)) = {x(1), x(2), ..., x(n)} and the edge set E(G(k,n)) ={x(i)x(i+1) : i=1,2, ...,n - k}boolean OR{x(n-k+1) x(j): j = n-k+2, n-k+3, ..., n}; the graph H-k,H-n is obtained from G(k,n) by adding all the edges x(i)x(j), where n-k+2 <= i < j <= n; and for even n >= 6 the graph Hn is obtained from G(n/2,n) by adding the edge x(n/2-1xn/2+2) and all the edges x(i)x(j), where n/2 + 3 <= i < j <= n. This study provides the proof to complete the above theorem.