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

グラフの疑似2-因子における非循環成分の数に関する注記

基本情報

論文ID: 2510.12155
タイトル: A note on the number of non-cycle components in a pseudo 2-factor of graphs
著者: Masaki Kashima (慶應義塾大学、横浜、日本)
分類: math.CO (組合論)
発表日: 2025年10月15日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.12155

要約

本論文は、グラフの疑似2-因子における非循環成分の数に関する問題を研究している。疑似2-因子は、各連結成分が $K_1$ 、 $K_2$ または循環である生成部分グラフである。Bekkaiと Kouiderは2009年に、すべてのグラフ $G$ は非循環成分の数が最大 $α(G)-δ(G)+1$ である疑似2-因子を持つことを証明した。本論文はこの結果を一般化し、すべてのグラフ $G$ は非循環成分の数が最大 $f(G)$ である疑似2-因子を持つことを証明する。ここで $f(G)$ は、すべての独立集合 $I$ に対する $|I|-δ_G(I)+1$ の最大値である。

研究背景と動機

中心的問題: グラフの疑似2-因子における非循環成分（すなわち $K_1$ または $K_2$ と同型な成分）の数の上界に関する研究。
問題の重要性:
- 2-因子はグラフ理論における古典的概念であり、ハミルトン循環と密接に関連している
- 疑似2-因子は2-因子の一般化として、孤立点と辺の存在を許容し、すべてのグラフが疑似2-因子を持つようにする
- 非循環成分の数の研究は、グラフの構造的性質の理解に役立つ
既存手法の限界:
- BekkaiとKouiderの結果は $α(G)-δ(G)+1$ の上界を与えるが、この界は十分に厳密でない可能性がある
- グラフの局所構造特性を考慮するより精密な分析が不足している
研究動機: 関数 $f(G)$ を導入することで、すべての独立集合の局所次数情報を考慮し、より正確な上界を得て、複数の既知結果を統一する。

核心的貢献

主定理: すべてのグラフ $G$ は非循環成分の数が最大 $\max\{0, f(G)\}$ である疑似2-因子を持つことを証明した。ここで $f(G) = \max\{|I| - δ_G(I) + 1 \mid I \text{は}G\text{の独立集合}\}$
理論の統一: この結果は以下を同時に一般化する：
- BekkaiとKouiderの疑似2-因子に関する結果（定理1）
- Niessenの2-因子存在性に関する結果（定理2）
- 著者の2-因子存在性に関する先行結果（定理3）
界の最適性: 新しい上界が最適であることを証明し、具体例を構成して界の最適性を示す
改善幅: 具体例を通じて、 $f(G)$ と $α(G)-δ(G)+1$ の差が任意に大きくなることを示す

方法の詳細

問題の定義

単純無向グラフ $G$ が与えられたとき、非循環成分の数ができるだけ少ない疑似2-因子を求める。疑似2-因子は $G$ の生成部分グラフであり、各連結成分は $K_1$ 、 $K_2$ または循環と同型である。

主要な技術的アプローチ

1. 準備的結果

観察5: 各木 $T$ と各葉 $u$ に対して、 $T$ は $u$ を含む最大独立集合を持つ
命題6: 各木 $T$ はちょうど $α(T)$ 個の成分を持つ疑似2-因子を持つ
命題7: 各森 $G$ はちょうど $α(G)$ 個の成分を持つ疑似2-因子を持つ

2. 主定理の証明戦略

証明は2つの主要なステップに分かれている：

ステップ1: 最大2-正則部分グラフの構成

$G$ における頂点素な循環の和 $F$ を選択し、 $|V(F)|$ ができるだけ大きくなるようにする
条件(a)を満たす前提で、 $G-V(F)$ における孤立点の数ができるだけ少なくなるようにする

ステップ2: 残りの森の処理

$H = G - V(F)$ を森とし、 $α = α(H)$ とする
命題7を利用して、 $H$ はちょうど $α$ 個の成分を持つ疑似2-因子を持つ
重要なのは $α ≤ f(G)$ を証明することである

3. 重要な補題

背理法により3つの重要な主張を証明する：

主張1: $H$ の頂点 $x$ に対して、 $x$ が $V(F)$ に2つの隣接頂点 $y_1, y_2$ を持つ場合、 $y_1^+y_2^+ \notin E(G)$

主張2: $H$ の各孤立頂点 $x$ に対して、 $V(F)$ に2つの頂点 $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$ を計算
新しい界が元の界より厳密に優れていることを示す

実験結果

主要な理論的結果

定理4 (主要結果): すべてのグラフ $G$ は非循環成分の数が最大 $\max\{0, f(G)\}$ である疑似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の界は正確である