期刊论文

Li, Shuchao

英文

Discrete Mathematics

0012-365X

2021

344

2

112226

10.1016/j.disc.2020.112226

The first author is financially supported by the National Natural Science Foundation of China (Grant No. 11801253 ), the Key Project of Education Department of Henan Province, PR China (Grant No. 19A110026 ) and the Cultivation Fund of Luoyang Normal University, PR China (Grant No. 2017-PYJJ-001 ). The second author is financially supported by the National Natural Science Foundation of China (Grant No. 11671164 ). The authors would like to express their sincere gratitude to referees for their valuable comments and suggestions, which led to a number of improvements to this paper.

本校为通讯机构

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...