2025-11-19T15:13:14.550330

Generalized toughness and Q-index in a graph

Zhou

Let $G$ be a graph. We denote by $c(G)$, $Î±(G)$ and $q(G)$ the number of components, the independence number and the signless Laplacian spectral radius ($Q$-index for short) of $G$, respectively. The toughness of $G$ is defined by $t(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G), c(G-S)\geq2\right\}$ for $G\neq K_n$ and $t(G)=+\infty$ for $G=K_n$. Chen, Gu and Lin [Generalized toughness and spectral radius of graphs, Discrete Math. 349 (2026) 114776] generalized this notion and defined the $l$-toughness $t_l(G)$ of a graph $G$ as $t_l(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subset V(G), c(G-S)\geq l\right\}$ if $2\leq l\leqÎ±(G)$, and $t_l(G)=+\infty$ if $l>Î±(G)$. If $t_l(G)\geq t$, then $G$ is said to be $(t,l)$-tough. In this paper, we put forward $Q$-index conditions for a graph to be $(b,l)$-tough and $(\frac{1}{b},l)$-tough, respectively.

academic

Generalized toughness and Q-index in a graph

基本信息

论文ID: 2510.10498
标题: Generalized toughness and Q-index in a graph
作者: Sizhong Zhou (江苏科技大学理学院)
分类: math.CO (组合数学)
发表时间: 2025年10月12日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.10498

摘要

本文研究图的广义韧性与Q-指数之间的关系。对于图 $G$ ，记 $c(G)$ 、 $\alpha(G)$ 和 $q(G)$ 分别表示图的连通分量数、独立数和无符号拉普拉斯谱半径(Q-指数)。传统韧性定义为 $t(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G), c(G-S)\geq2\right\}$ (对于 $G\neq K_n$ )。Chen, Gu和Lin将此概念推广为 $l$ -韧性： $t_l(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subset V(G), c(G-S)\geq l\right\}$ (当 $2\leq l\leq\alpha(G)$ 时)。本文提出了图成为 $(b,l)$ -韧性和 $(\frac{1}{b},l)$ -韧性的Q-指数充分条件。

研究背景与动机

问题背景

韧性概念的重要性: 图的韧性是由Chvátal在1973年引入的重要图论参数，它刻画了图的连通性和稳定性，与哈密顿回路、k-因子等图的结构性质密切相关。
谱理论的应用: 近年来，利用图的谱参数(如谱半径、拉普拉斯谱半径等)来刻画图的结构性质成为研究热点，谱条件往往比纯组合条件更易验证。
广义韧性的提出: Chen, Gu和Lin最近将传统韧性推广为 $l$ -韧性概念，这为研究图的韧性提供了更灵活的框架。

研究动机

理论完善: 虽然Chen等人已经建立了 $l$ -韧性与普通谱半径的关系，但Q-指数(无符号拉普拉斯谱半径)与 $l$ -韧性的关系尚未被研究。
方法统一: Q-指数在许多图论问题中都有重要应用，建立其与韧性的联系有助于统一不同研究领域的方法。
应用需求: 韧性条件在分数匹配、路径因子、k-可扩图等问题中都有应用，提供基于Q-指数的充分条件具有实际价值。

核心贡献

建立了Q-指数与 $(b,l)$ -韧性的关系: 给出了连通图 $G$ 满足 $t_l(G)\geq b$ 的Q-指数充分条件(定理1.1)。
建立了Q-指数与 $(\frac{1}{b},l)$ -韧性的关系: 给出了连通图 $G$ 满足 $t_l(G)\geq \frac{1}{b}$ 的Q-指数充分条件(定理1.2)。
提供了精确的极值图刻画: 对于两个主要定理，都给出了等号成立的充要条件，即极值图的完整刻画。
发展了新的证明技术: 利用商矩阵理论、图的谱性质和组合优化方法，为类似问题的研究提供了技术框架。

方法详解

任务定义

输入: 连通图 $G$ ，正整数 $b,l$ 输出: 判断 $G$ 是否为 $(b,l)$ -韧性或 $(\frac{1}{b},l)$ -韧性约束: 图 $G$ 的Q-指数需满足特定下界条件

核心定理

定理1.1 ( $(b,l)$ -韧性条件)

设 $b\geq 1$ , $l\geq 2$ 为整数， $G$ 是阶数为 $n$ 的连通图，其中 $n\geq \max\{(\frac{5}{2}b^2+4b+3)l-b^2-2b-5, \frac{(2b+1)l^2+(2b-3)l+2}{2}\}$ 。如果 $q(G)\geq q(K_{bl-1}\vee(K_{n-(b+1)l+2}\cup(l-1)K_1))$ 则 $t_l(G)\geq b$ ，除非 $G=K_{bl-1}\vee(K_{n-(b+1)l+2}\cup(l-1)K_1)$ 。

定理1.2 ( $(\frac{1}{b},l)$ -韧性条件)

设 $b\geq 2$ , $l\geq 2$ 为整数， $G$ 是阶数为 $n$ 的连通图，其中 $n\geq 6b\lceil\frac{l-1}{b}\rceil$ 。如果 $q(G)\geq q(K_{\lfloor\frac{l-1}{b}\rfloor}\vee(K_{n-\lfloor\frac{l-1}{b}\rfloor-l+1}\cup(l-1)K_1))$ 则 $t_l(G)\geq \frac{1}{b}$ ，除非 $G=K_{\lfloor\frac{l-1}{b}\rfloor}\vee(K_{n-\lfloor\frac{l-1}{b}\rfloor-l+1}\cup(l-1)K_1)$ 。