Families of graphs with twin pendent paths and the Braess edge

zbMATH Open1482.05318arXiv2112.03655MaRDI QIDQ5029434FDOQ5029434

Authors: Sooyeong Kim 

Publication date: 14 February 2022

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.

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

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

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

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)

Cites Work

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

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
• Kemeny's constant for nonbacktracking random walks
• A FAMILY OF BRUNNIAN LINKS BASED ON EDWARDS' CONSTRUCTION OF VENN DIAGRAMS
• 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)