Extremal hitting times of trees with some given parameters

Authors：Zhang, Huihui; Li, Shuchao^*

Source：LINEAR & MULTILINEAR ALGEBRA, 2022, 70(11): 2127-2149.

DOI：10.1080/03081087.2020.1789538

• Hitting time
• tree
• diameter
• matching number
• vertex bipartition
• leaf

Given a connected graph G=(V-G,E-G) with x,y is an element of 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 fromxtoy. 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 psi(G)=max(x,yVG)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 psi(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.