On the structure and values of betweenness centrality in dense betweenness-uniform graphs

0573762 - ÚI 2024 RIV CZ eng C - Konferenční příspěvek (zahraniční konf.)
Ghanbari, B. - Hartman, David - Jelínek, V. - Pokorná, Aneta - Šámal, R. - Valtr, P.
On the structure and values of betweenness centrality in dense betweenness-uniform graphs.
EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. Brno: MUNI Press, 2023 - (Kráľ, D.; Nešetřil, J.), s. 478-484. E-ISSN 2788-3116.
[EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./. Prague (CZ), 28.08.2023-01.09.2023]
Grant CEP: GA ČR(CZ) GA23-07074S
Institucionální podpora: RVO:67985807
Klíčová slova: betweenness * graphs
Obor OECD: Pure mathematics
https://journals.muni.cz/eurocomb/article/view/35600/31477

Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweenness-uniform (BUG)if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweenness-uniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value α for any rational numberαfrom the interval (3/4,∞) by showing that only very few betweenness centrality values below 6/7 are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweenness-uniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.
Trvalý link: https://hdl.handle.net/11104/0344131