Extremal hitting times of trees with some given parameters. Issue 11 (24th July 2022)

• Record Type: Journal Article
• Authors: Zhang, Huihui; Li, Shuchao
• Is Part Of: Linear & multilinear algebra. Volume 70:Issue 11(2022)
• Page Start: 2127
• Page End: 2149
• Publication Date: 2022-07-24
• Subjects: Hitting time -- tree -- diameter -- matching number -- vertex bipartition -- leaf; 05C12; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2020.1789538
• Languages: English
• ISSNs: 0308-1087

Abstract

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.