A Note on Hamiltonian Cycles in (k,n)-Factor-Critical Graphs

Ken‐ichi KawarabayashiSUT 2000 · DOI

This academic paper, published in the SUT Journal of Mathematics, explores a specific niche in graph theory: the intersection of Hamiltonian cycles (paths that visit every vertex exactly once and return to the start) and factor-critical graphs. Author Ken-ichi Kawarabayashi provides a mathematical proof for a conjecture that establishes degree-sum conditions required for these "sturdy" graphs to be Hamiltonian.

TL;DR

The paper proves a specific conjecture for $k=3$ and $k=4$ regarding $(k,n)$-factor-critical graphs. It shows that if these graphs meet a certain minimum degree sum for any three independent vertices ($\sigma_3$), they are guaranteed to contain a Hamiltonian cycle, barring a few well-defined exceptions.

What Problem Does This Paper Address?

In graph theory, finding a Hamiltonian cycle is a classic NP-complete problem. Because there is no simple "if and only if" test for all graphs, researchers look for sufficient conditions—properties that, if present, guarantee a cycle exists.

One common condition involves degree sums. For example, Ore’s Theorem states that if the sum of degrees of any two non-adjacent vertices is at least the total number of vertices, the graph is Hamiltonian. This paper looks at a more complex class of graphs called $(k,n)$-factor-critical graphs.

A graph is $(k,n)$-factor-critical if, after deleting any $n$ vertices, the remaining graph still contains a $k$-factor (a $k$-regular spanning subgraph). These graphs are essentially "robust"—you can damage them by removing vertices, and they still maintain a highly regular internal structure. The author seeks to prove that if such a graph is 2-connected and its vertices are "busy" enough (high degree sum), it must be Hamiltonian.

Methods

The paper is a theoretical mathematical proof. It doesn't use simulations or empirical data but relies on logical deduction and established lemmas in extremal graph theory. Key techniques include:

  • The Hopping Lemma: A classic tool in Hamiltonian graph theory (introduced by Woodall in 1973) used to analyze the properties of longest cycles and how they might be extended.
  • Proof by Contradiction: The author assumes a graph meets the degree conditions but is not Hamiltonian, then systematically demonstrates that this leads to a logical impossibility (e.g., violating the $(k,n)$-factor-critical property).
  • Toughness Analysis: The proof utilizes the concept of "1-tough" graphs. A graph is 1-tough if removing any set of vertices doesn't break the graph into more components than the number of vertices removed. This is a known necessary (but not always sufficient) condition for being Hamiltonian.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it does not use external datasets or benchmarks. The "objects" of study are abstract mathematical graphs.

Key Insights and Ideas

  • The $\sigma_3$ Threshold: The core of the conjecture is the condition $\sigma_3(G) \geq \frac{3}{2}(p - n - k)$. This means the sum of the degrees of any three independent vertices must be quite high relative to the total number of vertices ($p$), the number of vertices allowed to be deleted ($n$), and the regularity of the factor ($k$).
  • Bridging Factors and Cycles: A Hamiltonian cycle is essentially a 2-factor (a 2-regular spanning subgraph) that consists of a single circuit. By studying $(k,n)$-factor-critical graphs, the author is exploring how the existence of "lesser" factors (like $k$-factors) under certain constraints forces the existence of the "ultimate" factor: the Hamiltonian cycle.
  • Handling Exceptions: The paper acknowledges that the degree condition alone isn't enough; there are specific "exceptional" graph structures (often involving complete bipartite graphs) that satisfy the degree sum but aren't Hamiltonian. The proof successfully accounts for these by referencing a prior characterization of these non-1-tough exceptions.

Key Results

The primary result is the verification of Conjecture 1 for the cases where $k=3$ and $k=4$.

Specifically, the author proves that a 2-connected $(k,n)$-factor-critical graph of order $p$ with the specified $\sigma_3$ degree sum is Hamiltonian, provided $k \in \{3, 4\}$. This extends previous work that had already verified the conjecture for $k=1$ and $k=2$. This result tightens the mathematical understanding of how local vertex connectivity (degrees) influences global structure (Hamiltonicity) in robust graph families.

Limitations and Future Work

  • Specific $k$ Values: The proof is limited to $k=3$ and $k=4$. While this is a significant step forward, the general conjecture for all integers $k \geq 1$ remained open at the time of publication.
  • Connectivity Constraints: The results apply to 2-connected graphs. Exploring whether higher connectivity requirements could relax the degree sum condition is a potential avenue for further research.
  • Complexity of Exceptions: As $k$ increases, the number and complexity of exceptional graph structures that satisfy the degree condition but remain non-Hamiltonian may grow, making a general proof for all $k$ significantly more difficult.

Summary updated

Abstract

A graph G is said to be (k,n)-factor-critical if G−S has a k-factor for any S⊂V(G) with |S|=n. In [7], the author, Ota and Saito conjectured that if G is a 2-connected (k,n)-factor-critical graph of order p with σ3(G)≥32(p−n−k), then G is hamiltonian with some exceptions. In [7], the author, Ota and Saito also characterized all those graphs which satisfy the assumption of the conjecture, but are not 1-tough and, by using this, they verified the conjecture for k=1 and 2. In this paper, we verify the conjecture for k=3 and 4.
BibTeX
@inproceedings{kawarabayashi2000note,
  author = {Ken‐ichi Kawarabayashi},
  title = {{A Note on Hamiltonian Cycles in (k,n)-Factor-Critical Graphs}},
  booktitle = {SUT},
  year = {2000},
  doi = {10.55937/sut/991985618},
}
Figure