Families of graphs with twin pendent paths and the Braess edge

MaRDI QIDQ5029434zbMATH OpenFDO

Authors Sooyeong Kim

Publication date 14 February 2022

Full work available at URL https://arxiv.org/abs/2112.03655, https://journals.uwyo.edu/index.php/ela/article/view/5913

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Kemeny's constantrandom walk on a graphBraess edge

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Random walks on graphs (05C81)

Abstract: In the context of a random walk on an undirected graph, Kemeny's constant can measure the average travel time for a random walk between two randomly chosen vertices. We are interested in graphs that behave counter-intuitively in regard to Kemeny's constant: in particular, we examine graphs with a cut-vertex at which at least two branches are paths, regarding whether the insertion of a particular edge into a graph results in an increase of Kemeny's constant. We provide several tools for identifying such an edge in a family of graphs and for analising asymptotic behaviour of the family regarding the tendency to have that edge; and classes of particular graphs are given as examples. Furthermore, asymptotic behaviours of families of trees are described.

Recommendations

• The Braess' paradox for pendent twins
• A 1-separation formula for the graph Kemeny constant and Braess edges
• Complete multipartite graphs and Braess edges
• Kemeny's constant and an analogue of Braess' paradox for trees
• Computing Kemeny's constant for a barbell graph

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A Google-like model of road network dynamics and its application to regulation and control
• Complete multipartite graphs and Braess edges
• Computational Complexity
• Graphs and matrices
• Hitting time quasi-metric and its forest representation
• Kemeny's Constant and the Random Surfer
• Kemeny's constant and an analogue of Braess' paradox for trees
• Non-negative matrices and Markov chains.
• The Braess' paradox for pendent twins

Cited in

(9)

• 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
• A FAMILY OF BRUNNIAN LINKS BASED ON EDWARDS' CONSTRUCTION OF VENN DIAGRAMS
• Kemeny's constant for nonbacktracking random walks
• An Edge Centrality Measure Based on the Kemeny Constant
• The Braess' paradox for pendent twins
• A 1-separation formula for the graph Kemeny constant and Braess edges
• Kemeny's constant for a graph with bridges

This page was built for publication: Families of graphs with twin pendent paths and the Braess edge

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