More on betweenness-uniform graphs

Czechoslovak Mathematical Journal

Jana Coroničová Hurajová, Tomáš Madaras¹ 

关键词: betweenness centrality;    betweenness-uniform graph;   

DOI  :  10.21136/CMJ.2018.0087-16

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

  We study graphs whose vertices possess the same value of betweenness centrality (which is defined as the sum of relative numbers of shortest paths passing through a given vertex). Extending previously known results of S. Gago, J. Hurajová, T. Madaras (2013), we show that, apart of cycles, such graphs cannot contain 2-valent vertices and, moreover, are 3-connected if their diameter is 2. In addition, we prove that the betweenness uniformity is satisfied in a wide graph family of semi-symmetric graphs, which enables us to construct a variety of nontrivial cubic betweenness-uniform graphs.

【 授权许可】

Unknown