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