2025-11-10T02:54:44.514408

A note on the number of non-cycle components in a pseudo 2-factor of graphs

Kashima

A pseudo 2-factor of a graph is a spanning subgraph such that each component is $K_1$, $K_2$, or a cycle. This notion was introduced by Bekkai and Kouider in 2009, where they showed that every graph $G$ has a pseudo 2-factor with at most $Î±(G)-Î´(G)+1$ components that are not cycles. For a graph $G$ and a set of vertices $S$, let $Î´_G(S)$ denote the minimum degree of vertices in $S$. In this note, we show that every graph $G$ has a pseudo 2-factor with at most $f(G)$ components that are not cycles, where $f(G)$ is the maximum value of $|I|-Î´_G(I)+1$ among all independent sets $I$ of $G$. This result is a common generalization of a result by Bekkai and Kouider and a previous result by the author on the existence of a 2-factor.

academic

A note on the number of non-cycle components in a pseudo 2-factor of graphs

基本信息

论文ID: 2510.12155
标题: A note on the number of non-cycle components in a pseudo 2-factor of graphs
作者: Masaki Kashima (Keio University, Yokohama, Japan)
分类: math.CO (Combinatorics)
发表时间: October 15, 2025 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.12155

摘要

本文研究图的伪2-因子中非循环分量的数量问题。伪2-因子是一个生成子图，其中每个连通分量都是 $K_1$ 、 $K_2$ 或循环。Bekkai和Kouider在2009年证明了每个图 $G$ 都有一个伪2-因子，其非循环分量数至多为 $α(G)-δ(G)+1$ 。本文将此结果推广，证明每个图 $G$ 都有一个伪2-因子，其非循环分量数至多为 $f(G)$ ，其中 $f(G)$ 是所有独立集 $I$ 上 $|I|-δ_G(I)+1$ 的最大值。

研究背景与动机

核心问题: 研究图的伪2-因子中非循环分量（即同构于 $K_1$ 或 $K_2$ 的分量）数量的上界问题。
问题重要性:
- 2-因子是图论中的经典概念，与Hamilton循环密切相关
- 伪2-因子作为2-因子的推广，允许存在孤立点和边，使得每个图都存在伪2-因子
- 研究非循环分量的数量有助于理解图的结构性质
现有方法局限性:
- Bekkai和Kouider的结果给出了 $α(G)-δ(G)+1$ 的上界，但这个界可能不够紧
- 缺乏更精细的分析来考虑图的局部结构特征
研究动机: 通过引入函数 $f(G)$ ，考虑所有独立集的局部度数信息，获得更精确的上界，并统一多个已知结果。

核心贡献

主要定理: 证明了每个图 $G$ 都有一个伪2-因子，其非循环分量数至多为 $\max\{0, f(G)\}$ ，其中 $f(G) = \max\{|I| - δ_G(I) + 1 | I \text{是}G\text{的独立集}\}$
理论统一: 该结果同时推广了：
- Bekkai和Kouider关于伪2-因子的结果（定理1）
- Niessen关于2-因子存在性的结果（定理2）
- 作者之前关于2-因子存在性的结果（定理3）
界的紧性: 证明了新上界是最优的，通过构造具体例子说明界的紧性
改进幅度: 通过具体例子说明 $f(G)$ 和 $α(G)-δ(G)+1$ 之间的差距可以任意大

观察5: 对于每棵树 $T$ 和每个叶子 $u$ ， $T$ 有一个包含 $u$ 的最大独立集
命题6: 每棵树 $T$ 都有一个恰好包含 $α(T)$ 个分量的伪2-因子
命题7: 每个森林 $G$ 都有一个恰好包含 $α(G)$ 个分量的伪2-因子

2. 主定理证明策略

证明分为两个主要步骤：

步骤1: 构造最大2-正则子图

选择 $G$ 中顶点不相交的循环的并 $F$ ，使得 $|V(F)|$ 尽可能大
在满足条件(a)的前提下，使 $G-V(F)$ 中的孤立点数尽可能少

步骤2: 处理剩余森林

设 $H = G - V(F)$ 为森林， $α = α(H)$
利用命题7， $H$ 有一个恰好包含 $α$ 个分量的伪2-因子
关键是证明 $α ≤ f(G)$

3. 关键引理

通过反证法证明三个关键声明：

声明1: 对于 $H$ 中的顶点 $x$ ，如果 $x$ 在 $V(F)$ 中有两个邻居 $y_1, y_2$ ，则 $y_1^+y_2^+ \notin E(G)$

声明2: 对于 $H$ 的每个孤立顶点 $x$ ，存在 $V(F)$ 中的两个顶点 $y, y'$ 使得相应条件成立

声明3: 对于 $H$ 中度数为1的每个顶点 $x$ ，存在满足条件的邻居

技术创新点

精细化分析: 不仅考虑全局的独立数和最小度，还考虑每个独立集的局部最小度
构造性证明: 通过具体的图构造过程，展示如何找到满足条件的伪2-因子
统一框架: 将多个看似独立的结果纳入统一的理论框架

实验设置

本文是纯理论论文，没有实验部分，主要通过数学证明和构造性例子来验证结果。

构造性例子

例子1: 证明Bekkai-Kouider界的紧性

对于任意图 $H$ 和正整数 $p ≥ |V(H)| + 1$
构造图 $G_1$ ： $H$ 与 $p$ 个不相交 $K_2$ 的并
证明 $G_1$ 的每个伪2-因子至少有 $α(G_1) - δ(G_1) + 1$ 个非循环分量

例子2: 展示新界的优势

构造图 $G_2$ 包含顶点 $v_1, v_2$ ，独立集 $A_1, A_2$ （各含 $k$ 个顶点）和完全图 $B$
计算得出 $α(G_2) - δ(G_2) + 1 = k + 1$ ，而 $f(G_2) = 2$
说明新界严格优于原界

当每个独立集 $I$ 都满足 $δ_G(I) ≥ |I| + 1$ 时， $f(G) ≤ 0$ ，从而 $G$ 有2-因子
对于任意图 $G$ 和独立集 $I$ ，有 $|I| - δ_G(I) + 1 ≤ α(G) - δ(G) + 1$ ，因此 $f(G) ≤ α(G) - δ(G) + 1$
对于森林，定理4的界是精确的