Open AccessComputing Kemeny's constant for a barbell graph
Author(s) -
Jane Breen,
Steve Butler,
Nicklas Day,
Colt DeArmond,
Kate Lorenzen,
Haoyang Qian,
Jacob Riesen
Publication year - 2019
Publication title -
the electronic journal of linear algebra
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.447
H-Index - 31
eISSN - 1537-9582
pISSN - 1081-3810
DOI - 10.13001/ela.2019.5175
Subject(s) - mathematics , combinatorics , regular graph , distance regular graph , discrete mathematics , line graph , graph power , voltage graph , graph , spectral graph theory , null graph
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(n3), 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.