Original title: On the structure and values of betweenness centrality in dense betweenness-uniform graphs
Authors: Ghanbari, B. ; Hartman, David ; Jelínek, V. ; Pokorná, Aneta ; Šámal, R. ; Valtr, P.
Document type: Papers
Conference/Event: EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./, Prague (CZ), 20230828
Year: 2023
Language: eng
Abstract: 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.
Keywords: betweenness; graphs
Project no.: GA23-07074S (CEP)
Funding provider: GA ČR
Host item entry: EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
Note: Související webová stránka: https://journals.muni.cz/eurocomb/article/view/35600/31477

Institution: Institute of Computer Science AS ČR (web)
Document availability information: Fulltext is available in the digital repository of the Academy of Sciences.
Original record: https://hdl.handle.net/11104/0344131

Permalink: http://www.nusl.cz/ntk/nusl-528992


The record appears in these collections:
Research > Institutes ASCR > Institute of Computer Science
Conference materials > Papers