Publikace na Matematicko-fyzikální fakulta |

2023

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 greater than 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.