Extremal problems on k-ary trees with respect to the cover cost and reverse cover cost

作者：Li, Shuchao; Wang, Shujing^*

来源：Discrete Mathematics, 2021, 344(8): 112432.

DOI：10.1016/j.disc.2021.112432

• k-ary tree
• Cover cost
• Reverse cover cost
• Totally balanced

Let T-n,T-k be the set of k-ary trees of order n = (k - 1)t + 2, where k-ary trees are trees in which every vertex has degree 1 or k. For a connected graph G = (V (G), E(G)), the cover cost (resp. reverse cover cost) of a vertex u in G is defined as CCG(u) = Sigma(v is an element of V(G)) H-vu (resp. RCG(u) = Sigma(v is an element of V(G)) H-vu), where H-uv is the expected hitting time for random walk beginning at u to visit v. In this paper, we consider extremal problems on k-ary trees with respect to the cover cost and reverse cover cost. In particular, the maximum (resp. minimum) cover cost and reverse cover cost among all k-ary trees with given order are identified.