A 1-separation formula for the graph Kemeny constant and Braess edges

DOI10.1007/S10910-021-01294-8MaRDI QIDQ2072215zbMATH OpenOpenAlexFDO

Authors Nolan Faught, Mark Kempton, Adam Knudson

Publication date 26 January 2022

Published in Journal of Mathematical Chemistry (Search for Journal in Brave)

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

zbMATH Keywords

effective resistancegraph connectivityKemeny's constantresistance distance

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Kemeny's constant of a simple connected graph $G$ is the expected length of a random walk from $i$ to any given vertex $jeqi$. We provide a simple method for computing Kemeny's constant for 1-separable via effective resistance methods from electrical network theory. Using this formula, we furnish a simple proof that the path graph on $n$ vertices maximizes Kemeny's constant for the class of undirected trees on $n$ vertices. Applying this method again, we simplify existing expressions for the Kemeny's constant of barbell graphs and demonstrate which barbell maximizes Kemeny's constant. This 1-separation identity further allows us to create sufficient conditions for the existence of Braess edges in 1-separable graphs. We generalize the notion of the Braess edge to Braess sets, collections of non-edges in a graph such that their addition to the base graph increases the Kemeny constant. We characterize Braess sets in graphs with any number of twin pendant vertices, generalizing work of Kirkland et.~al.~cite{kirkland2016kemeny} and Ciardo cite{ciardo2020braess}.

Recommendations

• The Braess' paradox for pendent twins
• Kemeny's constant and an analogue of Braess' paradox for trees
• Kemeny's constant for a graph with bridges
• Families of graphs with twin pendent paths and the Braess edge
• Complete multipartite graphs and Braess edges

Cites work

• Computing Kemeny's constant for a barbell graph
• Kemeny's constant and an analogue of Braess' paradox for trees
• Kemeny's Constant and the Random Surfer
• Resistance distance in straight linear 2-trees
• Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant
• The Braess' paradox for pendent twins
• The Kemeny constant for finite homogeneous ergodic Markov chains
• Über ein Paradoxon aus der Verkehrsplanung

Cited in

(18)

• Kemeny's constant for a graph with bridges
• The Braess' paradox for pendent twins
• Kemeny's constant for several families of graphs and real-world networks
• Kemeny's constant and the effective graph resistance
• Kemeny's constant and an analogue of Braess' paradox for trees
• Families of graphs with twin pendent paths and the Braess edge
• 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
• An Edge Centrality Measure Based on the Kemeny Constant
• 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
• Cut-edge centralities in an undirected graph
• 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: A 1-separation formula for the graph Kemeny constant and Braess edges

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