On betweenness-uniform graphs
On betweenness-uniform graphs
复制标题
关于介数均匀图
DOI：
--
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
T. Madaras
中科院分区：
文献类型：
--
作者：
Silvia Gago;J. Hurajová;T. Madaras
图的顶点的介数中心度是通过该顶点的所有顶点对之间的最短路径的分数。本文研究了顶点具有相同介数中心度值的图（介数一致图）的性质和构造，证明了这一性质对距离正则图（包括强正则图）和通过图克隆和局部连接操作得到的各种图都成立.此外，我们证明了，对于足够大的n，有超多项式的许多介数均匀图的n个顶点，并探讨结构的介数均匀图具有一个普遍或次普遍的顶点。
The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distanceregular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large n, there are superpolynomially many betweenness-uniform graphs on n vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.