Extremal cover cost and reverse cover cost of trees with given segment sequence

摘要

A segment of a tree T is a path whose end vertices have degree 1 or at least 3, while all internal vertices have degree 2. The lengths of all the segments of T form its segment sequence, in analogy to the degree sequence. 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 H-v is an element of v(G)(uv) (resp. RCG(u) = Sigma(v is an element of V(G)) H-vu), where Hut, is the expected hitting time for random walk beginning at u to visit v. In this paper, the unique tree with the minimum cover cost and minimum reverse cover cost among all trees with given segment sequence are characterized. Furthermore, the unique tree with the maximal reverse cover cost among all trees with given segment sequence are also identified. (C) 2019 Elsevier B.V. All rights reserved.