Kemeny's constant and Kirchhoffian indices for conjoined highly symmetric graphs

被引：1
作者：
Palacios, Jose Luis [1 ]
Markowsky, Greg [2 ]
机构：
[1] Univ New Mexico, Elect & Comp Engn Dept, Albuquerque, NM 87131 USA
[2] Monash Univ, Dept Math, Melbourne, Vic, Australia
来源：
DISCRETE APPLIED MATHEMATICS | 2021年 / 302卷
关键词：
Hitting times of random walk; Kemeny's constant; Electric resistance; Kirchhoff's index; Highly symmetric graphs; Edge-transitive graphs;
D O I：
10.1016/j.dam.2021.07.007
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Bouquet graphs consist of the conjoining at a single vertex of a collection of (possibly distinct) pieces which are highly symmetric graphs. We find closed form formulas for Kemeny's constant and two Kirchhoffian indices for bouquet graphs in terms of the parameters of the component pieces. We also provide some general results on highly symmetric graphs, and prove in particular that regular edge-transitive graphs are highly symmetric. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页码：215 / 220
页数：6
相关论文
共 15 条
  • [1] [Anonymous], 1997, Introduction to Probability
  • [2] Buckley F., 1990, Distance in Graphs
  • [3] Chandra A. K., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P574, DOI 10.1145/73007.73062
  • [4] Devroye L., 1990, J THEORET PROBAB, V4, P497
  • [5] Folkman J., 1967, J. Combin. Theory, V3, P215, DOI DOI 10.1016/S0021-9800(67)80069-3
  • [6] Georgakopoulos A, WALK REGULAR GRAPHS
  • [7] Kemeny's constant for several families of graphs and real-world networks
    Kooij, Robert E.
    Dubbeldam, Johan L. A.
    [J]. DISCRETE APPLIED MATHEMATICS, 2020, 285 : 96 - 107
  • [8] Broder and Karlin's Formula for Hitting Times and the Kirchhoff Index
    Luis Palacios, Jose
    Renom, Jose M.
    [J]. INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2011, 111 (01) : 35 - 39
  • [9] On the Kirchhoff Index of Regular Graphs
    Luis Palacios, Jose
    [J]. INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2010, 110 (07) : 1307 - 1309
  • [10] Random walks on edge transitive graphs
    Palacios, JL
    Renom, JM
    [J]. STATISTICS & PROBABILITY LETTERS, 1998, 37 (01) : 29 - 34
12