On Kemeny's constant for trees with fixed order and diameter

DOI10.1080/03081087.2020.1796905MaRDI QIDQ5095243zbMATH OpenOpenAlexFDO

Authors Lorenzo Ciardo, Geir Dahl, S. J. Kirkland

Publication date 5 August 2022

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2003.08286

zbMATH Keywords

caterpillarKemeny's constantMarkov chainrandom walk on a graphstochastic matrix

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of graph theory to circuits and networks (94C15)

Abstract: Kemeny's constant $kappa(G)$ of a connected graph $G$ is a measure of the expected transit time for the random walk associated with $G$. In the current work, we consider the case when $G$ is a tree, and, in this setting, we provide lower and upper bounds for $kappa(G)$ in terms of the order $n$ and diameter $delta$ of $G$ by using two different techniques. The lower bound is given as Kemeny's constant of a particular caterpillar tree and, as a consequence, it is sharp. The upper bound is found via induction, by repeatedly removing pendent vertices from $G$. By considering a specific family of trees - the broom-stars - we show that the upper bound is asymptotically sharp.

Recommendations

• Kemeny's constant and Wiener index on trees
• Kemeny's constant for a graph with bridges
• Bounds on Kemeny's constant of trees with a prescribed matching number
• Kemeny's constant and an analogue of Braess' paradox for trees
• Kemeny's constant for several families of graphs and real-world networks

Cites work

• Combinatorics, Paul Erdős is eighty. Vol. 1
• Complete multipartite graphs and Braess edges
• Control Techniques for Complex Networks
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Kemeny's constant and an analogue of Braess' paradox for trees
• Kemeny's constant and the effective graph resistance
• Kemeny's Constant and the Random Surfer
• Non-negative matrices and Markov chains. 2nd ed
• The Braess' paradox for pendent twins
• The Kemeny constant for finite homogeneous ergodic Markov chains
• The Kirchhoff indexes of some composite networks
• The role of Kemeny's constant in properties of Markov chains

Cited in

(14)

• On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees
• Bounds on Kemeny's constant of trees with a prescribed matching number
• Kemeny's constant and an analogue of Braess' paradox for trees
• Computing Kemeny's constant for a barbell graph
• On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival
• Kemeny's constant and Wiener index on trees
• On Kemeny's constant and stochastic complement
• Extremal hexagonal chains with respect to the Kemeny's constant
• Mean first passage time and Kemeny's constant using generalized inverses of the combinatorial Laplacian
• Edge addition and the change in Kemeny's constant
• Kemeny's constant and enumerating Braess edges in trees
• Threshold graphs, Kemeny's constant, and related random walk parameters
• On average hitting time and Kemeny's constant for weighted trees
• Cacti with extremal Kemeny's constants

This page was built for publication: On Kemeny's constant for trees with fixed order and diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5095243)