Extremal Graphs with Respect to Vertex Betweenness Centrality for Certain Graph Families

Abstract

In this paper, we consider the graph-theoretical concept of the betweenness centrality measure. Our attention is focused on the determination of the extremal betweenness values within the various families of graphs. We prove that the maximum
betweenness value is reached for the maximum degree vertex of the fan graph (resp. the wheel graph) in the class of 2-connected (resp. 3-connected) graphs. In addition, we study the family of graphs with prescribed maximum degree as well as the class of graphs with diameter at least 3. Moreover, the extremal graphs between all graphs of minimum degree at least 2 or 3 are found. At the end, we describe some illustrative computations with real-world networks, which indicate that the real betweenness values deviate from the proven maximum values. Nevertheless, the purpose of the proven maximum values can be found in the normalization of the betweenness centrality measure.