Hamiltonian Properties of 3-Connected Claw-Free Graphs and Line Graphs of 3-Hypergraphs

This paper establishes that, with specific exceptions, every 3-connected claw-free graph with a domination number of at most 5 is Hamiltonian and every such graph with a domination number of at most 4 is Hamilton-connected, while also proving that 3-connected line graphs of 3-hypergraphs with a domination number of at most 4 are Hamiltonian.

The Gist

Imagine a city made entirely of intersections (dots) and roads (lines connecting them). In the world of mathematics, this is called a graph.

This paper is about finding the perfect "tour" through such a city. Specifically, the authors are looking for two types of tours:

1. The Hamiltonian Cycle: A route that drives through every single intersection exactly once and returns to the start. (Like a perfect loop around a city).
2. The Hamilton-Connected Path: A route that starts at any intersection and ends at any other intersection, visiting every single one in between. (Like a delivery driver who can start at any warehouse and end at any customer's house, hitting every stop along the way).

The paper focuses on a specific type of city layout called a "claw-free" graph.

• The "Claw": Imagine a central intersection with three roads branching out to three other intersections, but none of those three outer intersections connect to each other. It looks like a bird's claw.
• Claw-Free: These cities are designed so that this specific "claw" shape never appears. They are more tightly knit.

The researchers are trying to answer a big question: "How few 'key intersections' do we need to control to guarantee that a perfect tour exists?"

In math terms, this is the Domination Number. Think of a "dominating set" as a team of security guards. If you place guards at a few key intersections, and every other intersection in the city is either where a guard is standing or right next to a guard, you have "dominated" the city. The "Domination Number" is the smallest number of guards needed to cover the whole city.

The Big Discovery

For a long time, mathematicians knew that if a city was "2-connected" (meaning you can't disconnect it by removing just one road) and had a very small number of guards (2 or fewer), a perfect loop tour was guaranteed.

But what happens if the city is even more robust? What if it's "3-connected" (you'd have to remove at least three roads to break it apart)?

The authors of this paper cracked the code for these super-strong cities:

1. The Loop Guarantee: If a 3-connected, claw-free city has 5 or fewer guards covering it, you are guaranteed a perfect loop tour (Hamiltonian), unless the city is a very specific, weird exception (related to the famous "Petersen Graph," which is like a mathematical "monster" that breaks all the rules).
2. The Any-Start/Any-End Guarantee: If that same city has 4 or fewer guards, you are guaranteed a tour that can start and end anywhere (Hamilton-connected), unless it's another specific type of weird exception (related to the "Wagner Graph").

The "Hypergraph" Twist

The paper also dives into a more complex version of these cities called 3-Hypergraphs.

• In a normal city, a road connects two intersections.
• In a "3-hypergraph" city, a "road" (or hyperedge) can connect three intersections at once. It's like a three-way roundabout that instantly links three places.

The authors proved that even in these complex, three-way-connected cities, if the city is strong (3-connected) and can be covered by just 4 guards, a perfect loop tour is guaranteed.

Why Does This Matter?

Think of it like optimizing a delivery network or a computer chip.

• Efficiency: If you know your network is "claw-free" and you know how few "control points" (domination number) you have, you can mathematically guarantee that data or goods can flow through the entire system without getting stuck or needing to backtrack.
• The "Best Possible" Bound: The authors didn't just find a rule; they found the tightest rule. They proved that if you try to lower the number of guards to 4 for the loop guarantee, or 3 for the any-start guarantee, the rule breaks (because of those "monster" exception graphs). They found the exact tipping point where the math works perfectly.

Summary Analogy

Imagine you are a tour guide in a massive, intricate theme park (the graph).

• The Claw-Free Rule: The park is designed so no single ride station has three dead-end paths leading to nowhere.
• The 3-Connected Rule: The park is so well-built that you'd have to close three major bridges to isolate a section.
• The Guard Count: You have a team of security guards (dominating set) patrolling key spots.

The Paper's Conclusion:
"If your theme park is built this way, and you have 5 or fewer guards, you can promise a guest a tour that hits every single ride and returns to the start. If you have 4 or fewer guards, you can promise a tour that starts at any ride and ends at any other ride, hitting everything in between. The only time this promise fails is if the park is built on a very specific, bizarre blueprint (the Petersen or Wagner graphs) that nature just doesn't allow in normal parks."

This work helps mathematicians and engineers understand exactly how much "connectivity" and "coverage" is needed to ensure a system is fully traversable.

Technical Summary

Here is a detailed technical summary of the paper "Hamiltonian Properties of 3-Connected Claw-Free Graphs and Line Graphs of 3-Hypergraphs" by Kenta Ozeki and Leilei Zhang.

1. Problem Statement and Motivation

The paper addresses the Hamiltonicity (existence of a Hamilton cycle) and Hamilton-connectedness (existence of a Hamilton path between any two distinct vertices) of specific classes of graphs, primarily claw-free graphs and line graphs of 3-hypergraphs.

• Context: The research is motivated by Thomassen's Conjecture (1986), which posits that every 4-connected line graph is Hamiltonian. This was later strengthened to suggest that every 4-connected claw-free graph is Hamiltonian (and even Hamilton-connected).
• Gap in Knowledge: While sufficient conditions for 2-connected claw-free graphs were established by Ageev (1994) based on the domination number ($\gamma(G)$), specifically that $\gamma(G) \le 2$ implies Hamiltonicity, the bounds for 3-connected graphs were not fully characterized. Previous results (e.g., by Vrána, Zhan, and Zhang) showed that for 3-connected claw-free graphs, $\gamma(G) \le 3$ implies Hamilton-connectedness.
• Objective: The authors aim to:
  1. Determine the best possible upper bound on the domination number $\gamma(G)$ that guarantees Hamiltonicity and Hamilton-connectedness for 3-connected claw-free graphs.
  2. Extend these results to line graphs of 3-hypergraphs, investigating the relationship between domination number and Hamiltonicity in this broader context.

2. Methodology and Tools

The authors employ a combination of structural graph theory, closure operations, and reduction techniques involving multigraphs and hypergraphs.

• Closure Operations:
  • Ryjáček's Closure ($cl(G)$): A transformation for claw-free graphs where local completions are applied at "eligible" vertices. A key property is that $G$ is Hamiltonian if and only if $cl(G)$ is Hamiltonian.
  • M-Closure ($cl_M(G)$): A strengthened closure operation introduced by Ryjáček and Vrána to preserve Hamilton-connectedness, which the standard closure does not always guarantee.
• Line Graph Preimages:
  • Utilizing the correspondence between a line graph $G$ and its preimage multigraph $H$ (where $G = L(H)$).
  • Using the concept of the core of a multigraph ($co(H)$), obtained by suppressing degree-2 vertices and removing pendant edges.
  • Applying theorems linking dominating closed trails in $H$ to Hamilton cycles in $L(H)$, and $(e_1, e_2)$-internally dominating trails (IDT) in $H$ to Hamilton paths in $L(H)$.
• Reduction to Petersen and Wagner Graphs:
  • The proofs rely heavily on Theorem 2.6 (Chen et al.) and Theorem 2.7 (Liu et al.), which state that if a 3-edge-connected multigraph does not contain a specific trail through a set of vertices, it can be contracted to the Petersen graph ($P$).
  • The Wagner graph ($W$) is used as an exceptional case for Hamilton-connectedness, derived from the Petersen graph.
• Hypergraph Incidence Graphs:
  • For 3-hypergraphs, the authors use the incidence graph $IG(H)$, converting the problem of finding a Hamilton cycle in $L(H)$ to finding a dominating closed $W$-quasitrail in $IG(H)$ (where $W$ represents white vertices corresponding to hyperedges).

3. Key Contributions and Results

A. Hamiltonicity in 3-Connected Claw-Free Graphs

The authors establish the tightest possible bound for Hamiltonicity in 3-connected claw-free graphs.

• Theorem 1.5: Let $G$ be a 3-connected claw-free graph. If $\gamma(G) \le 5$, then $G$ is Hamiltonian, unless its closure $cl(G)$ is the line graph of a graph belonging to a specific exceptional class $\mathcal{P}'$.
  • Class $\mathcal{P}'$: Graphs derived from the Petersen graph by attaching pendant edges or subdividing incident edges at each vertex, such that the edge domination number is $\le 5$.
  • Significance: This generalizes Ageev's result (which was for 2-connected graphs with $\gamma \le 2$) to 3-connected graphs with $\gamma \le 5$. The bound of 5 is shown to be best possible.

B. Hamilton-Connectedness in 3-Connected Claw-Free Graphs

The authors refine the bound for the stronger property of Hamilton-connectedness.

• Theorem 1.6: Let $G$ be a 3-connected claw-free graph. If $\gamma(G) \le 4$, then $G$ is Hamilton-connected, unless its M-closure $cl_M(G)$ is the line graph of a graph belonging to the exceptional class $\mathcal{W}'$.
  • Class $\mathcal{W}'$: Graphs derived from the Wagner graph via specific operations (attaching pendant/double edges, subdividing) such that the edge domination number is $\le 4$.
  • Significance: This improves upon the previous result (Vrána et al.) which required $\gamma(G) \le 3$. The authors prove that $\gamma(G) \le 4$ is sufficient, identifying the exact structural exceptions.

C. Hamiltonicity in Line Graphs of 3-Hypergraphs

The paper extends the findings to the broader class of line graphs of 3-hypergraphs.

• Theorem 1.8: Every 3-connected line graph of a 3-hypergraph with domination number at most 4 is Hamiltonian.
  • Significance: This generalizes Theorem 1.2 (Ageev) and Theorem 1.5. It confirms that the domination number bound of 4 is sufficient for Hamiltonicity in this specific hypergraph context.
  • Sharpness: The authors demonstrate that the bound is sharp by showing that graphs with $\gamma(G) = 5$ (derived from the Petersen graph) can be non-Hamiltonian.
  • Counterexamples for Hamilton-Connectedness: The paper notes that even with $\gamma(G) = 1$, a 3-connected line graph of a 3-hypergraph (e.g., $K_{1,2,3}$) may fail to be Hamilton-connected, highlighting a distinction between Hamiltonicity and Hamilton-connectedness in this domain.

4. Proof Strategy Overview

1. Reduction to Closure: The problem is reduced to analyzing the closure $cl(G)$ (or $cl_M(G)$), which is a line graph of a triangle-free graph (or multigraph).
2. Translation to Preimage: The Hamiltonicity of the line graph is translated into the existence of a dominating closed trail (or IDT) in the preimage multigraph $H$.
3. Core Analysis: The problem is further reduced to the core $co(H)$, which is 3-edge-connected.
4. Domination Set Mapping: A dominating set of size $k$ in $G$ corresponds to a set of edges in $H$ that dominate all edges. These map to a set of vertices in $co(H)$.
5. Application of Extremal Theorems:
   • If the core contains a trail through the mapped vertices, the graph is Hamiltonian.
   • If not, Theorem 2.6/2.7 implies the core contracts to the Petersen graph (or Wagner graph).
6. Structural Characterization: The authors analyze the preimages of the Petersen/Wagner vertices. They prove that if the domination number is within the bound (5 for Hamiltonicity, 4 for Hamilton-connectedness), the structure of these preimages forces the existence of the required trail, unless the graph belongs to the explicitly defined exceptional classes ($\mathcal{P}'$ or $\mathcal{W}'$).

5. Significance and Impact

• Resolution of Open Bounds: The paper settles the question of the optimal domination number bounds for Hamiltonicity and Hamilton-connectedness in 3-connected claw-free graphs, moving beyond the previously known bounds of 2 and 3.
• Unification of Conjectures: By linking domination number constraints to the famous Thomassen and Matthews-Sumner conjectures, the work provides a deeper understanding of the structural requirements for Hamiltonicity.
• Extension to Hypergraphs: The results on 3-hypergraphs bridge the gap between standard graph theory and hypergraph theory, showing that domination number constraints remain powerful even in the more complex setting of hypergraphs.
• Exceptional Graphs: The precise characterization of the exceptional graphs (based on Petersen and Wagner graphs) provides a complete classification, which is crucial for algorithmic applications and further theoretical developments.

In summary, this paper provides a definitive characterization of Hamiltonian properties in 3-connected claw-free graphs and 3-hypergraph line graphs based on domination numbers, utilizing advanced closure techniques and structural reductions to the Petersen and Wagner graphs.