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

DOI10.1080/03081087.2020.1796905zbMATH Open1494.05100arXiv2003.08286OpenAlexW3047171013MaRDI QIDQ5095243FDOQ5095243

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

Publication date: 5 August 2022

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

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.

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

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

zbMATH Keywords

Markov chainstochastic matrixcaterpillarKemeny's constantrandom walk on a graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Kemeny's constant and Wiener index on trees
• Kemeny's constant and an analogue of Braess' paradox for trees
• On Kemeny's constant and stochastic complement
• On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival
• On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees
• Computing Kemeny's constant for a barbell graph
• Bounds on Kemeny's constant of trees with a prescribed matching number

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)