2023/12/30 by Babak Ghanbari, Ghanbari, Babak, David E. Hartman +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2401.00347
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 characterise all the BUGs with betweennes 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.