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 (Keio University, Yokohama, Japan)
분류: 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 | 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. 주요 정리 증명 전략

증명은 두 가지 주요 단계로 나뉜다:

단계 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: 새로운 상한의 우월성 제시

꼭짓점 $v_1, v_2$ , 독립 집합 $A_1, A_2$ (각각 $k$ 개 꼭짓점 포함), 완전 그래프 $B$ 를 포함하는 그래프 $G_2$ 구성
$α(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의 상한이 정확하다