2021/05/14 by David E. Hartman, Hartman, David, Aneta Pokorná +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2105.06777
openalex publication_date 2021/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Betweenness centrality is a measure of the importance of a vertex x inside a network based on the fraction of shortest paths passing through x. We study a blow-up construction that has been shown to produce graphs with uniform distribution of betweenness. We disprove the conjecture about this procedure's universality by showing that trees with a diameter at least three cannot be transformed into betweenness-uniform by the blow-up construction. It remains open to characterize graphs for which the blow-up construction can produce betweenness-uniform graphs.