Discrete Mathematics and Combinatorics Commons^™

Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan

Theory and Applications of Graphs

The betweenness centrality of an edge e is, summed over all u,v ∈ V(G), the ratio of the number of shortest u,v-paths in G containing e to the number of shortest u,v-paths in G. Graphs whose vertices all have the same edge betweenness centrality are called edge betweeness-uniform. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl´orez , and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive. In this paper we present new results involving properties of betweenness-uniform graphs.