广义分裂图的谱半径与哈密顿性

《Discrete Mathematics》:Spectral radius and Hamiltonicity in generalized split graphs

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

编辑推荐:

   **摘要** 一个图 $\hat{G}$ 是分裂图,如果它的顶点集可以被划分为一个团 $S$ 和一个独立集 $I$,且交叉边连接 $S$ 中的一个顶点与 $I$ 中的一个顶点。广义分裂图 $G$ 是由分裂图 $\hat{G}$ 通过对 $I$ 中的每个顶点 $v$ 用一个大

  

**摘要**

一个图 $\hat{G}$ 是分裂图,如果它的顶点集可以被划分为一个团 $S$ 和一个独立集 $I$,且交叉边连接 $S$ 中的一个顶点与 $I$ 中的一个顶点。广义分裂图 $G$ 是由分裂图 $\hat{G}$ 通过对 $I$ 中的每个顶点 $v$ 用一个大小为 $k \geq 2$ 的团 $S_v$ 进行替换而得到的,其中如果 $uv \in E(\hat{G})$,则添加 $u$ 与 $S_v$ 之间的所有边。为简便起见,将广义分裂图记为 $G = (S, \bigcup_{v \in I} S_v)$。在本文中,我们给出了连通广义分裂图中存在哈密顿圈的一个充分谱半径条件,其中 $|S| \geq \max\{(k+3)|I|+3, 4k^2+4k-2\}$。此外,我们刻画了在所有具有 $S$ 与 $\bigcup_{v \in I} S_v$ 之间有 $e(S, \bigcup_{v \in I} S_v) = k(|I|+q)$ 条边的连通广义分裂图 $G = (S, \bigcup_{v \in I} S_v)$ 中谱半径最大的极图,其中 $q \in \{0,1\} \cup [k^2+7k-1, |S|-1]$。这些结果扩展了 Zhu、Fan 和 Lin(2025)[43] 所得到的主要结果。

**引言**

图 $G$ 中的一个哈密顿圈是经过 $G$ 的所有顶点的圈。如果图 $G$ 具有哈密顿圈,则称 $G$ 为哈密顿图。哈密顿性是图论中的核心主题之一,在大量文献中得到了广泛研究,例如参见 [1]、[6]、[11]、[12]、[13]、[28]、[29]、[30]、[31] 以及综述 [20]。

判断一个图是否为哈密顿图(即评估其哈密顿性)是一个众所周知的 NP-完全问题。由于这种计算上的困难性,寻找一般的充分条件——那些保证图 $G$ 中存在哈密顿圈的条件——已成为图论中最持久且充满活力的研究主题之一。

这一研究方向的两个基础性结果如下。一是 Dirac 定理 [15]:对于一个 $n$ 个顶点的图 $G$($n \geq 3$),如果最小度满足 $\delta(G) \geq n/2$,则 $G$ 包含一个哈密顿圈。另一个是 Chvátal-Erd?s 准则 [11]:如果图 $G$($|V(G)| \geq 3$)的连通度 $\kappa(G)$ 至少与它的独立数 $\alpha(G)$ 一样大,则 $G$ 是哈密顿的。

如果对于每个满足 $\omega(G-S) > 1$ 的 $S \subseteq V(G)$ 子集,都有 $|S| \geq t \cdot \omega(G-S)$,则称图 $G$ 是 $t$-坚韧的,其中 $\omega(G)$ 表示 $G$ 的连通分量数。$G$ 的坚韧度 $t(G)$ 定义如下:
$$t(G) = \begin{cases} \min\left\{\frac{|S|}{\omega(G-S)} : S \subseteq V(G), \omega(G-S) > 1\right\}, & \text{如果 } G \neq K_n; \\ \infty, & \text{如果 } G = K_n. \end{cases}$$

显然,1-坚韧是一个图具有哈密顿圈的必要条件。反过来,Chvátal [10] 提出了以下猜想:

**猜想 1.1 [10]** 存在一个常数 $t_0$,使得每个 $t_0$-坚韧的图都包含一个哈密顿圈。

关于这一猜想,Enomoto 等人 [16] 猜想 $t_0 = 2$。2000年,Bauer、Broersma 和 Veldman [3] 否证了这一结果;他们进一步观察到,如果这样的 $t_0$ 存在,则 $t_0 \geq 9/4$。随着研究的推进,哈密顿圈的存在性已在一些图的类别中被深入研究:Kratsch 等人证明了 $3/2$-坚韧的分裂图是哈密顿的 [27];Liu 等人 [37] 证明了分裂图是哈密顿的当且仅当完全圈可延展的(每个顶点在一个3-圈上,非哈密顿圈可延展),且 $r$-连通的 $K_{1,r}$-自由分裂图($r \in \{3,4\}$)是哈密顿连通性的。Matthews 和 Sumner [39] 猜想4-连通的无爪图是哈密顿的;Li [34] 给出了3-连通图具有哈密顿性的最小度准则。其他种类图的哈密顿圈存在性也得到了研究,例如弦图 [2]、[25],无三角形图 [4]。Gu 等人 [21] 获得了以下结果:超图 $H$ 的线图具有哈密顿圈当且仅当 $H$ 有一个支配的欧拉子超图。

随着研究的进展,人们越来越认识到图的特征值可以用来研究图的哈密顿性。设 $G = (V(G), E(G))$ 是一个阶数为 $n = |V(G)|$、大小为 $m = |E(G)|$ 的有限简单无向图。设 $A = A(G)$ 为其邻接矩阵。由于 $A$ 是对称非负矩阵,其特征值可以排列为 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$,且 $\lambda_1$ 非负,并且在 $A$ 的所有特征值中具有最大的绝对值。最大特征值 $\lambda_1$ 称为 $G$ 的谱半径,记为 $\rho(G)$。如果 $G$ 是连通的,则 $A(G)$ 是不可约的,根据非负矩阵的 Perron-Frobenius 理论(参见 [14]),$\rho(G)$ 的代数重数为1,并且存在一个与 $\rho(G)$ 对应的唯一正单位特征向量。我们将这样的特征向量称为 $G$ 的 Perron 向量。其分量可以视为顶点权重。

1986年,Brualdi 和 Solheid [8] 提出了以下谱问题。

**问题 1** 在指定的一类图中,$n$ 个顶点的图 $G$ 的最大谱半径是多少?

此后不久,以下重要的顶点谱 Turán 型问题得到了密集研究:

**问题 2** 对于给定的一类图 $\mathcal{F}$,不含 $\mathcal{F}$ 中任何成员的 $n$ 个顶点的图 $G$ 的最大谱半径是多少?

迄今为止,问题2已在广泛的情形中得到了处理——最值得关注的包括 $\mathcal{F}$ 为短奇圈的情形 [33]、不相交的颜色关键图 [32]、路径因子 [23]、$[a,b]$-因子 [22]、不相交的非颜色关键图 [9]。当 $\mathcal{F}$ 为仅由一个哈密顿圈组成的单元素集时,引起了大量关注。该领域一个古老且著名的猜想指出:任何 $d$-正则 $n$ 个顶点的图 $G$,如果其第二大绝对特征值至多为 $d/c$(其中 $c > 0$ 为某个普适常数),则具有哈密顿圈。该猜想已由 Glock、Correia 和 Sudakov [18] 解决。Fiedler 和 Nikiforov [17] 开启了图中哈密顿圈存在的谱半径条件的研究。Lu、Liu 和 Tian [38] 研究了利用图的谱半径和二分图的拟补来给出二分图中哈密顿圈的充分条件。Li 和 Ning [35] 建立了 $\delta(G) \geq 2$ 的图 $G$ 的哈密顿性的充分谱半径条件。随后,Benediktovich [5] 对此进行了推广。最近,Zhu、Fan 和 Lin [43] 给出了连通分裂图中哈密顿圈存在的谱半径条件。

直接受 [43] 的启发,我们从谱的角度研究广义分裂图的哈密顿性。我们首先证明如果一个广义分裂图是 $3/2$-坚韧的,则它具有哈密顿圈。基于这一结果,我们给出了保证连通广义分裂图中存在哈密顿圈的谱半径下界。

一个图 $\hat{G}$ 是分裂图,如果它的顶点集可以被划分为一个团 $S$ 和一个独立集 $I$,且交叉边连接 $S$ 中的一个顶点与 $I$ 中的一个顶点。广义分裂图 $G$ 是由分裂图 $\hat{G}$ 通过对 $I$ 中的每个顶点 $v$ 用一个大小为 $k$ 的团 $S_v$ 进行替换而得到的,其中如果 $uv \in E(\hat{G})$,则添加 $u$ 与 $S_v$ 之间的所有边。为简便起见,将广义分裂图记为 $G = (S, \bigcup_{v \in I} S_v)$。

给定一个完全图 $K_s$ 和 $t$ 个 $k$ 阶完全图的不相交并 $tK_k$,我们按如下方式构造广义分裂图:首先,在 $K_s$ 的一个顶点子集(记为 $V_1$)与 $tK_k$ 的所有顶点之间添加所有可能的边,其中 $0 < |V_1| = s_1 < s$。其次,在 $V(K_s) \setminus V_1$ 与 $t_1K_k$ 的顶点之间添加所有可能的边,其中 $0 < t_1 < t$。将所得的图记为 $G_k(s_1, s-s_1; t_1, t-t_1)$。

我们的第一个主要结果建立了连通广义分裂图中存在哈密顿圈的充分谱半径条件。

**定理 1.1** 设 $G = (S, \bigcup_{v \in I} S_v)$ 是一个连通广义分裂图,$|S| = s$,$|I| = t$,$S_v$ 是大小为 $k$ 的团,其中 $s \geq \max\{(k+3)t+3, 4k^2+4k-2\}$,$t \geq 3$,$k \geq 2$。如果 $\rho(G) \geq \rho(G_k(1, s-1; 1, t-1))$,则 $G$ 包含一个哈密顿圈,除非 $G \cong G_k(1, s-1; 1, t-1)$。

给定一个完全图 $K_s$ 和 $t$ 个不相交的完全图 $K_k$:首先,选取一个顶点 $r \in V(K_s)$ 并添加 $r$ 到 $tK_k$ 中每个顶点的所有可能的边;然后,从 $K_s$ 中再选取另外 $q$ 个顶点,并在这些 $q$ 个顶点与一个 $K_k$ 的顶点之间添加所有可能的边。我们将所得的图记为 $H_{k,q}^{s,t}$。

我们的下一个主要结果刻画了所有具有 $S$ 与 $\bigcup_{v \in I} S_v$ 之间有 $e(S, \bigcup_{v \in I} S_v) = k(|I|+q)$ 条边的连通广义分裂图 $G = (S, \bigcup_{v \in I} S_v)$ 中谱半径最大的极图,其中 $q \in \{0,1\} \cup [k^2+7k-1, |S|-1]$。

**定理 1.2** 设 $G = (S, \bigcup_{v \in I} S_v)$ 是一个广义分裂图,$|S| = s$,$|I| = t$,$|S_v| = k$,$e(S, \bigcup_{v \in I} S_v) = k(t+q)$。如果 $s \geq t \geq 1$,$k \geq 2$ 且 $q \in \{0,1\} \cup [k^2+7k-1, s-1]$,则 $\rho(G) \leq \rho(H_{k,q}^{s,t})$,等号成立当且仅当 $G \cong H_{k,q}^{s,t}$。

**本文结构。** 在本节余下部分,我们介绍必要的符号和术语。在第2节中,我们给出相关的预备知识。在第3节中,基于广义分裂图的 $3/2$-坚韧性,我们逐步完善极图的结构并完成定理1.1的证明。在第4节中,我们给出定理1.2的证明。最后一节给出一些总结性评论。

**符号与术语。** 设 $G$ 是一个图。$G$ 中两个顶点 $u$ 和 $v$ 如果由一条边相连则称为相邻(或邻居)。如果 $uv \in E(G)$,用 $G-uv$(或 $G-u$)表示从 $G$ 中删除边 $uv$(或顶点 $u$)所得的图。当删除多条边(或顶点)时,该记号自然推广。类似地,如果 $uv \notin E(G)$,用 $G+uv$ 表示在 $G$ 中添加 $u$ 和 $v$ 之间一条边所得的图。对于 $V(G)$ 的两个不相交顶点子集 $V_1$ 和 $V_2$,$G[V_1]$ 表示 $G$ 由 $V_1$ 导出的子图,$G[V_1, V_2]$ 表示由 $V_1$ 和 $V_2$ 之间的边导出的子图。$G[V_1]$ 和 $G[V_1, V_2]$ 的边数可简记为 $e(V_1)$ 和 $e(V_1, V_2)$。顶点 $v$ 在 $G$ 中的邻居集记为 $N_G(v)$,其大小为 $v$ 在 $G$ 中的度,记为 $d_G(v)$。对于顶点 $v \in V(G)$ 和子集 $W \subseteq V(G)$,令 $N_W(v) = N_G(v) \cap W$,$d_W(v) = |N_W(v)|$。对于正整数 $t$,集合 $\{1, 2, \ldots, t\}$ 简记为 $[t]$。

**第2节**

**预备知识**

在本节中,我们给出一些预备知识,这些知识将用于证明我们的主要结果。首先,我们回顾商矩阵理论。

设 $M$ 是一个实 $n \times n$ 矩阵,令 $X = \{1, 2, \ldots, n\}$。给定 $X$ 的一个划分为 $\pi: X = X_1 \cup X_2 \cup \cdots \cup X_k$,矩阵 $M$ 可以相应地划分为

$$M = \begin{pmatrix} M_{1,1} & M_{1,2} & \cdots & M_{1,k} \\ M_{2,1} & M_{2,2} & \cdots & M_{2,k} \\ \vdots & \vdots & \ddots & \vdots \\ M_{k,1} & M_{k,2} & \cdots & M_{k,k} \end{pmatrix}$$

$M$ 关于 $\pi$ 的商矩阵定义为 $k \times k$ 矩阵 $B_\pi = (b_{i,j})_{i,j=1}^k$,其中 $b_{i,j}$ 是 $M_{i,j}$ 中所有行和的平均值。划分 $\pi$

**定理1.1的证明**

在本节中,我们给出定理1.1的证明,该定理提供了连通广义分裂图中存在哈密顿圈的充分谱半径条件。

**定理1.1的证明**

反设图 $G = (S, \bigcup_{v \in I} S_v)$ 在满足 $|S| = s$,$|I| = t$,$S_v$ 是大小为 $k$ 的团的条件下不包含哈密顿圈。根据引理2.7,可以取一个顶点子集 $M \subseteq V(G)$,$|M| = m$,使得 $m$ 尽可能小,并且

$$\frac{m}{\omega(G-M)} < \frac{3}{2}$$

我们声称 $M \subset S$。否则,设 $|M \cap S| = m_1$,则 $m_1 < $

**定理1.2的证明**

在本节中,我们给出定理1.2的证明,该定理刻画了所有具有 $S$ 与 $\bigcup_{v \in I} S_v$ 之间有 $e(S, \bigcup_{v \in I} S_v) = k(|I|+q)$ 条边的连通广义分裂图 $G = (S, \bigcup_{v \in I} S_v)$ 中谱半径最大的图,其中 $q \in \{0,1\} \cup [k^2+7k-1, |S|-1]$。

**定理1.2的证明**

设 $G' \in \mathcal{G}_k(t+q)_{s,kt}$ 是达到最大谱半径的连通广义分裂图。将 $V(G')$ 划分为 $V_1 \cup V_2$,其中 $V_1 = V(K_s) = \{u_1, \ldots, u_s\}$,$V_2 = \bigcup_{v \in I} S_v$。设 $x$ 为 $A(G')$ 的 Perron 向量,$\rho = \rho(G')$。由

**总结性评论**

我们建立了广义分裂图中存在哈密顿圈的谱半径条件。这些结果扩展了之前关于分裂图的工作 [43],为这些图类的谱性质提供了新的见解。

未来工作可包括将这些结果推广到横截版本。给定图系统 ??={???,???,…,???},其公共顶点集 V 的大小为 n,若 V 上的 m 边图 H 存在一个双射 ??:E(H)→[m],使得 e∈E(G_??(e)),则称 H 为 ?? 的横截图。致谢我们衷心感谢审稿人提出的宝贵意见和建设性建议,这些建议极大地帮助提升了本文的清晰度、严谨性和表述质量。李书超得到国家自然科学基金(项目编号 12571365、12171190)以及教育部重点实验室"非线性分析与应用"开放研究基金(项目编号 NAA2025ORG010)的资助。陈鑫选|耿霞燕|李书超|余元田
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号