Structure of betweenness uniform graphs with low values of betweenness centrality

Abstract

This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago, Coroni\v{c}ov\'a-Hurajov\'a and Madaras conjectured that for every rational \(\alpha\ge 3/4\) there exists a BUG having betweenness centrality~\(\alpha\). We disprove this conjecture, and provide an alternative view of the structure of betweenness-uniform graphs from the point of view of their complement. This allows us to characterise all the BUGs with betweennes centrality at most 9/10, and show that their betweenness centrality is equal to \(\frac{\ell}{\ell+1}\) for some integer \(\ell\le 9\). We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than~1.