Scholarlink

<p>Kemeny’s constant of a simple connected graph <i>G</i> is the average travel time for a random walk to reach a randomly target vertex selected according to the stationary distribution, which is an important parameter reflecting the structural properties of <i>G</i>. A <i>cactus</i> is a connected graph in which every block is either a single edge or a cycle. In this paper, we address the problem of determining the graph that maximizes (or minimize) the Kemeny’s constant among all cacti. We identify the extremal cacti that attain the maximum and the minimum values of Kemeny’s constants among all cacti of order <i>n</i> with <i>t</i> cycles, respectively.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Cacti with Extremal Kemeny’s Constants

  • 期刊论文

  • 发表日期：

    2026年5月13日

查看全文
  • Yirong Zheng,
  • Longjian Liao,
  • Jianxi Li

摘要

Kemeny’s constant of a simple connected graph G is the average travel time for a random walk to reach a randomly target vertex selected according to the stationary distribution, which is an important parameter reflecting the structural properties of G. A cactus is a connected graph in which every block is either a single edge or a cycle. In this paper, we address the problem of determining the graph that maximizes (or minimize) the Kemeny’s constant among all cacti. We identify the extremal cacti that attain the maximum and the minimum values of Kemeny’s constants among all cacti of order n with t cycles, respectively.