On the connectivity and the diameter of betweenness-uniform graphs

0576896 - ÚI 2025 NL eng J - Journal Article
Hartman, David - Pokorná, Aneta - Valtr, P.
On the connectivity and the diameter of betweenness-uniform graphs.
Discrete Applied Mathematics. Roč. 342, January 2024 (2024), s. 27-37. ISSN 0166-218X. E-ISSN 1872-6771
R&D Projects: GA ČR(CZ) GA23-07074S
Institutional support: RVO:67985807
Keywords : Betweenness centrality * Betweenness-uniform * Connectivity * Distance
OECD category: Pure mathematics
Impact factor: 1.1, year: 2022
Method of publishing: Limited access
https://dx.doi.org/10.1016/j.dam.2023.08.017

Betweenness centrality is a centrality measure based on the overall amount of shortest paths passing through a given vertex. A graph is betweenness-uniform if all its vertices have the same betweenness centrality. We study the properties of betweenness-uniform graphs. In particular, we show that every connected betweenness-uniform graph is either a cycle or a 3-connected graph. Also, we show that betweenness uniform graphs of high maximal degree have small diameter.
Permanent Link: https://hdl.handle.net/11104/0346289