On the (reverse) cover cost of trees with some given parameters

作者：Zhang, Huihui; Li, Shuchao^*

来源：Discrete Mathematics, 2021, 344(2): 112226.

DOI：10.1016/j.disc.2020.112226

• Hitting time
• Cover cost
• Reverse cover cost
• Diameter
• Matching number

For a connected graph G = (V-G, E-G), the cover cost of a vertex u in G is defined as CCG(u) = Sigma(v is an element of VG) H-uv and the reverse cover cost of a vertex v in G is defined as RCG(v) = Sigma(u is an element of VG) H-uv, where H-uv is the expected hitting time for random walk beginning at u to visit v. These two parameters were introduced as tractable variants of cover time on a graph. In this paper, some extremal problems on the (reverse) cover cost of a vertex in a tree with given graph parameters are considered. Firstly, the sharp lower bound on the cover cost among all n-vertex trees with given diameter (resp. matching number, domination number, vertex bipartition) is established. Secondly, the sharp lower bound on the reverse cover cost among all n-vertex trees with given diameter (resp. matching number, domination number) is established. All the corresponding extremal graphs are identified, respectively. At last, the unique n-vertex tree with given number of leaves having the minimum cover cost (resp. reverse cover cost) is characterized.