Kemeny's constant for a graph with bridges

DOI10.1016/J.DAM.2022.08.004MaRDI QIDQ2081463zbMATH OpenOpenAlexFDO

Authors Jane Breen, Emanuele Crisostomi, Sooyeong Kim

Publication date 13 October 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

2-tree spanning forestKemeny's constantresistance matrix

Mathematics Subject Classification ID

Connectivity (05C40) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: In this paper, we determine a formula for Kemeny's constant for a graph with multiple bridges, in terms of quantities that are inherent to the subgraphs obtained upon removal of all bridges and that can be computed independently. With the formula, we consider several optimization problems for Kemeny's constant for graphs with bridges, and we remark on the computational benefit of this formula for the computation of Kemeny's constant. Finally, we discuss some potential applications.

Recommendations

• A 1-separation formula for the graph Kemeny constant and Braess edges
• Computing Kemeny's constant for a barbell graph
• 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

Cites work

• A 1-separation formula for the graph Kemeny constant and Braess edges
• A Google-like model of road network dynamics and its application to regulation and control
• Alleviating road network congestion: traffic pattern optimization using Markov chain traffic assignment
• Directed forests and the constancy of Kemeny's constant
• Families of graphs with twin pendent paths and the Braess edge
• Hitting time quasi-metric and its forest representation
• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 6506585 (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.
• Random walk centrality and a partition of Kemeny's constant.
• Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant
• The electrical resistance of a graph captures its commute and cover times
• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Why is Kemeny's constant a constant?

Cited in

(14)

• A 1-separation formula for the graph Kemeny constant and Braess edges
• Kemeny's constant for several families of graphs and real-world networks
• Kemeny's constant and the Kirchhoff index for the cluster of highly symmetric graphs
• Kemeny's constant and the effective graph resistance
• On Kemeny's constant for trees with fixed order and diameter
• Computing Kemeny's constant for a barbell graph
• Kemeny's constant and Wiener index on trees
• Extremal hexagonal chains with respect to the Kemeny's constant
• Bounds on Kemeny's constant of a graph and the Nordhaus-Gaddum problem
• Cut-edge centralities in an undirected graph
• Edge addition and the change in Kemeny's constant
• Threshold graphs, Kemeny's constant, and related random walk parameters
• Two kinds of polygonal chains with extremal Kemeny's constants
• Cacti with extremal Kemeny's constants

This page was built for publication: Kemeny's constant for a graph with bridges

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