Constructions of Betweenness-Uniform Graphs from Trees

Authors: David Hartman, A. Pokorná
Publication year: 2021
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Extended Abstracts EuroComb 2021
Bibliographic citation: HARTMAN, David, POKORNÁ, A. Constructions of Betweenness-Uniform Graphs from Trees. In: NEŠETŘIL, J., PERARNAU, G., RUÉ, J., SERRA, O., eds. Extended Abstracts EuroComb 2021. Cham: Birkhäuser / Springer, 2021, S. 732-738. Trends in Mathematics, 14. ISBN 978-3-030-83822-5. ISSN 2297-0215
Dostupné z: doi:10.1007/978-3-030-83823-2_117.
DOI: 10.1007/978-3-030-83823-2_117
ID: 545088

Abstract

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.