Extremal hitting times of trees with some given parameters. Issue 11 (24th July 2022) - Zhang, Huihui; Li, Shuchao
Abstract : Given a connected graph G = ( V G, E G ) with x, y ∈ V G, the hitting time H G ( x, y ) is defined as the expected number of steps that a simple random walk takes to go from x to y . A hitting-time-based invariant, called the ZZ index, was first proposed by Zhu and Zhang [The hitting time of random walk on unicyclic graphs. Linear Multilinear Algebra. doi:10.1080/03081087.2019.1611732 ] recently. It was defined to be ψ ( G ) = max x, y ∈ V G H G ( x, y ) . In this paper, some extremal problems on the ZZ index of trees with some given parameters are considered. Firstly, sharp upper and lower bounds on ψ ( G ) are determined, respectively, for trees with given diameter, matching number, given vertex bipartition and given pendant numbers. Secondly, ordering the n -vertex caterpillar trees with respect to their ZZ indices are established.