Structure of betweenness uniform graphs with low values of betweenness centrality

Abstrakt

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čová-Hurajová and Madaras conjectured that for every rational α ≥ 3/4 there exists a BUG having betweenness centrality α. 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 characterize all the BUGs with betweenness centrality at most 9/10, and show that their betweenness centrality is equal to ℓ / (ℓ + 1) for some integer ℓ ≤ 9. We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than 1.