Average Distance, Connected Hub Number and Connected Domination Number
Xiao-Lu Gao, Shou‐Jun Xu · Lanzhou University Institutional Repository · 2019
Let G be a connected graph of given order n and let mu(G) denote the average of all the distances between any two distinct vertices in G. The connected hub number h(c)(G) (resp., the connected domination number gamma(c)(G)) of G is the smallest order of a connected subgraph S of G such that each pair of nonadjacent vertices outside S are joined by a path with all internal vertices in S (resp., each vertex outside S is adjacent to one vertex of S). It is easy to see that h(c)(G) <= gamma(c)(G) <= h(c)(G) + 1. In view of the close relationship between the two invariants, we can partition connected graphs into two classes and according to this partition, give sharp upper bounds on mu(G) of the two classes of G in terms of h(c)(G), respectively, and further characterize the extremal graphs. As a corollary, we give sharp tipper bounds on mu(G) in terms of h(c)(G), and characterize the extremal graphs. Since these graphs are trees, we further address the problem about 2-connected graphs and give some initial properties and results.