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

摘要

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.

关键词