COMPUTING KEMENY'S CONSTANT FOR BARBELL-TYPE GRAPHS
COMPUTING KEMENY'S CONSTANT FOR BARBELL-TYPE GRAPHS
复制标题
DOI：
10.13001/1081-3810.4095
复制
发表时间：
2019-11-01
影响因子：
0.7
通讯作者：
Riesen, Jacob
中科院分区：
文献类型：
--
作者：
Breen, Jane;Butler, Steve;Riesen, Jacob
在图论中，凯梅尼常数（英语：Kemeny's constant）是一个图形参数，它测量了在图的顶点上的随机游走中的平均首次通过时间的加权平均值。在某种意义上，凯梅尼常数是衡量图的“连通性”的一个指标。一个明确的计算这个参数的图阶n组成的两个大集团加入了任意数量的平行路径的长度相等，以及两个集团加入了两个路径的长度不同。在每种情况下，Kemeny常数都是O（n（3）），这是n个顶点的图的Kemeny常数的最大可能阶。所使用的方法是基于有趣的技术，在谱图理论，并包括一个推广使用双子图找到一个图的频谱。
In a graph theory setting, Kemeny's constant is a graph parameter which measures a weighted average of the mean first passage times in a random walk on the vertices of the graph. In one sense, Kemeny's constant is a measure of how well the graph is 'connected'. An explicit computation for this parameter is given for graphs of order n consisting of two large cliques joined by an arbitrary number of parallel paths of equal length, as well as for two cliques joined by two paths of different length. In each case, Kemeny's constant is shown to be O(n(3)), which is the largest possible order of Kemeny's constant for a graph on n vertices. The approach used is based on interesting techniques in spectral graph theory and includes a generalization of using twin subgraphs to find the spectrum of a graph.