关于凯门伊常数的极值多边形链

《Discrete Applied Mathematics》:Extremal polygonal chains with respect to the Kemeny’s constant

【字体: 大 中 小 】 时间:2026年09月26日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   ## 摘要 设 $G$ 为一个连通图。$G$ 的 Kemeny 常数记为 $\kappa(G)$,表示从一个固定起始顶点出发,到达按照平稳分布随机选取的目标顶点所需的期望时间。该常数是一个源自马尔可夫链理论的重要图不变量,在图论中引起了广泛关注。本文结合电网络方法与关于 S

  

## 摘要

设 $G$ 为一个连通图。$G$ 的 Kemeny 常数记为 $\kappa(G)$,表示从一个固定起始顶点出发,到达按照平稳分布随机选取的目标顶点所需的期望时间。该常数是一个源自马尔可夫链理论的重要图不变量,在图论中引起了广泛关注。本文结合电网络方法与关于 S、T-异构体的 Kemeny 常数比较结果,刻画了关于 Kemeny 常数的最大和最小多边形链。这将 Yang 和 Li(2026)关于六边形链以及 Liao 等人(2026)关于五边形链的结果推广到具有任意给定有序面长序列的一般多边形链。

## 引言

Kemeny 常数是度量图上随机游走连通性的重要指标。它最初为遍历马尔可夫链定义,给出随机游 walker 到达随机选取的目标顶点所需的期望时间,且与起始顶点无关。这使其成为衡量图连通程度的一个有用且内在的度量,数值越小表明图越容易遍历。由于其可解释性,Kemeny 常数在图论中 [1], [2], [3], [4], [5], [6] 和应用网络分析中 [7], [8], [9], [10], [11] 吸引了越来越多的关注。

设 $G=(V(G),E(G))$ 为一个具有 $|V(G)|=n$ 个顶点和 $|E(G)|=m$ 条边的连通图。记 $d_i^G$ 为顶点 $i$ 在 $G$ 中的度数。严格地,$G$ 的 Kemeny 常数记为 $\kappa(G)$,表示从固定起始顶点出发到达按照平稳分布随机选取的目标顶点所需的期望时间,其数学表达式为 $\kappa(G)=\sum_{j\neq i}\frac{d_j^G}{2m}E_i[T_j]$,其中 $E_i[T_j]$ 表示从 $i$ 到 $j$ 的均值首次到达时间(或击中时间),即从顶点 $i$ 出发的随机游走者第一次到达 $j$ 所需的期望时间。"常数"一词反映了这一关键事实:该值不依赖于起始顶点 $i$ 的选择:对于图中任意固定起点,该值均保持不变。这一基本性质由 Kemeny 和 Snell [12] 首次建立。

Kemeny 常数存在概率、谱和组合三种表达式,为分析提供了多种工具。值得注意的是,Kemeny 常数也可以用电阻距离来解释 [13]。定义在图 $G$ 上的经典距离函数是任意两个顶点 $u$ 和 $v$ 之间的(最短路径)距离,记为 $d_G(u,v)$,即连接它们的最短路径的长度。如果我们将图 $G$ 的每条边替换为一个单位电阻,并将 $G$ 视为电网络 $N$,则 $G$ 中顶点 $u$ 和 $v$ 之间的电阻距离 [14] 记为 $\Omega_G(u,v)$,定义为 $N$ 中对应节点 $u$ 和 $v$ 之间的净有效电阻。Palacios 和 Renom [13] 建立了以下恒等式。

$$\kappa(G)=\frac{1}{4m}\sum_{u\in V(G)}\sum_{v\in V(G)}d_u^G d_v^G \Omega_G(u,v) \tag{1.2}$$

另一方面,Chen 和 Zhang [15] 引入了一个基于电阻距离的图不变量,称为 $G$ 的乘性度-Kirchhoff 指标,定义如下。

$$K_f^*(G)=\frac{1}{2}\sum_{u\in V(G)}\sum_{v\in V(G)}d_u^G d_v^G \Omega_G(u,v) \tag{1.3}$$

结合式 (1.2)、(1.3) 可知,$\kappa(G)$ 和 $K_f^*(G)$ 相差一个比例因子。

作为重要的图不变量,Kemeny 常数吸引了大量研究关注 [16], [17], [18], [19], [20], [21]。该领域的一个核心问题是在给定图族中刻画使 Kemeny 常数最小化或最大化的图。因此,大量近期工作致力于刻画关于 Kemeny 常数的极值图结构。沿此方向,Breen 等人 [22] 猜想哑铃图在所有连通图中取得最大 Kemeny 常数。随后在 2022 年,Faught、Kempton 和 Knudson [23] 证明路径图在所有连通树中取得最大 Kemeny 常数。后来,Ciardo、Dahl 和 Kirkland [24] 刻画了给定阶数和直径的所有树中 Kemeny 常数最小的极值图。Jang、Kim 和 Song [25] 建立了给定直径的树取得最大 Kemeny 常数的必要条件。Zeng [26] 分别刻画了取得最大和最小 Kemeny 常数的加权树。最近,Yang 和 Li [27] 刻画了关于 Kemeny 常数的极值六边形链。Liao、Chen 和 Li [28] 确定并刻画了所有五边形链和所有多联苯链中分别具有最大和最小 Kemeny 常数的极值链。受这些优秀工作的启发,本文考虑关于 Kemeny 常数的极值多边形链。具体地,对于给定的有序面长序列 $(k_1,\ldots,k_n)$,其中 $k_i\geq 4$,$1\leq i\leq n$,我们刻画了具有该有序面长序列的所有多边形链中取得 Kemeny 常数最大值和最小值的链。文献 [27], [28] 中考虑的五边形链和六边形链分别对应于所有 $1\leq i\leq n$ 时 $k_i=5$ 和 $k_i=6$ 的特殊情形,而本文处理的是任意给定的有序面长序列 $(k_1,\ldots,k_n)$,其中 $k_i\geq 4$。

下面,我们引入一些相关记号来描述多边形链。外平面图是所有顶点均位于外侧面边界上的平面图。多边形链 $P_n$ 是一个 2-连通外平面图,满足以下条件:(i) $P_n$ 有 $n$ 个内侧面,且每个内侧面的长度至少为四;(ii) 任意两个内侧面恰好共享一条边,或互不相交;(iii) 每个顶点的度数为 2 或 3。为便于表述,记 $P_n$ 的多边形面分别为 $H_1,H_2,\ldots,H_n$,使得 $H_i$ 与 $H_{i+1}$ 相邻($1\leq i\leq n-1$),并设 $k_i$ 为 $H_i$ 的长度。以下,外平面嵌入仅用于参数化描述,多边形链被视为抽象图而非具有固定嵌入的平面图。

设 $Q_n$ 表示由 $n$ 个正方形 $S_1,S_2,\ldots,S_n$ 组成的多边形链。则多边形链 $P_n$ 可以通过向 $Q_n$ 的第 $i$ 个正方形 $S_i$ 添加 $k_i-4$ 个顶点来获得。注意,向每个面 $S_i$ 添加这 $k_i-4$ 个新顶点有 $k_i-3$ 种方式,即向 $S_i$ 的上边添加 0(或 1, 2, …, $k_i-4$)个顶点,其余顶点添加到下边。显然,对于终端正方形 $S_1$ 和 $S_n$,是否将顶点添加到下边或上边不改变多边形链 $P_n$ 的结构性质。为简化起见,本研究假设 $H_1$ 和 $H_n$ 是通过向 $S_1$ 和 $S_n$ 的上边添加 0 个顶点构建的。对于其余的每个多边形 $H_i$($2\leq i\leq n-1$),我们根据其顶行上新增顶点的数量赋予 $H_i$ 一个符号 $h_i\in\{0,1,2,\ldots,k_i-4\}$。基于上述构造过程,多边形链 $P_n$ 可以由特殊参数 $H=(h_2,h_3,\ldots,h_{n-1})$ 确定,以下我们将其记为 $P(H)$ [29]。

最后,我们介绍一些特殊的多边形链。如果 $P(H)$ 的所有多边形均具有偶数(奇数)个顶点,则称 $P(H)$ 为偶(奇)多边形链。如果多边形链 $P(H)$ 满足对所有 $2\leq i\leq n-1$ 有 $h_i=\frac{k_i-4}{2}$ 的条件,则称为线性多边形链(非唯一确定),记为 $LP_n$。多边形链中的弯折是指非终端多边形,其符号为 0 或 $k_i-4$。每个多边形都是弯折的多边形链称为"全弯折"链。在"全弯折"链中,一种特殊类型是螺旋烯多边形链,记为 $HP_n$,其表示为 $P(\underbrace{0,0,\ldots,0}_{n-2})$(同构于 $P(\underbrace{k_2-4,k_3-4,\ldots,k_{n-1}-4}_{n-2})$)。例如,$HP_4$ 和 $LP_4$ 如图 1 所示。

## 章节摘要

### 预备知识

本节首先引入后续使用的一些相关记号。

在有机化学中,异构体是具有相同分子式但不同结构式的两种化合物。作为异构体的一种特殊类型,S、T-异构体的概念由 Polansky 和 Zander [30] 于 1982 年引入,可按图论定义为如下。

**定义 2.1 S、T-异构体** 假设存在两个无公共顶点的图 $A$ 和 $B$,其中 $u,v\in A$($u\neq v$)且 $x,y\in B$($x\neq y$)。设 $S$ 为由 $A$ 和 $B$ 构成的图……

### 关于 Kemeny 常数的极值多边形链

本节中,多边形链被视为在图同构意义下的抽象图;具体而言,链的反射和反转视为相同的。

设 $P(H)$ 为包含 $n$ 个多边形的多边形链,其中 $H=(h_2,h_3,\ldots,h_{n-1})$。如图 3 所示,$P(H)$ 中的多边形依次标记为 $H_1,H_2,\ldots,H_n$。为便于表述,将相邻多边形的公共边标记为 $a_1b_1,a_2b_2,\ldots,a_{n-1}b_{n-1}$,并将终端多边形 $H_n$ 标记为 $a_{n-1},b_{n-1},u_1,u_2,\ldots,u_{k_n-2}$。我们

### 结论

本文刻画了使 Kemeny 常数最小化和最大化的多边形链。对于给定的有序面长序列,唯一的最小化者为螺旋烯多边形链,而任何最大化者必须是线性多边形链。这将之前关于五边形链和六边形链的结果推广到具有任意给定有序面长序列的一般多边形链。

## 利益冲突声明

作者声明不存在可能影响本文所述工作的已知竞争性经济利益或个人关系。

## 致谢

作者感谢匿名审稿人对本文的仔细阅读和宝贵意见。作者感谢国家自然科学基金(通过资助号 12671419)和山东省泰山学者专项资金(通过资助号 tstp202607065)的支持。

**胡凯颖 | 孙文胜 | 杨玉军**
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号