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


Jelena Klisara, Jana Coroničová Hurajová, Tomáš Madaras, Riste Škrekovski




The betweenness centrality of a vertex in a graph is the sum of relative numbers of shortest paths that pass through that vertex. We study extremal values of vertex betweenness within various families of graphs. We prove that, in the family of 2-connected (resp. 3-connected) graphs on $n$ vertices, the maximum betweenness value is reached for the maximum degree vertex of the fan graph $F_{1,n-1}$ (resp. the wheel graph $W_n$); the maximum betweenness values, their realizing vertices and extremal graphs are determined also for wider families of graphs of minimum degree at least 2 or 3, respectively, and, in addition, for graphs with prescribed maximum degree or prescribed diameter at least 3.