Characterizing forbidden pairs for Hamiltonian squares

DOI10.1007/S00373-015-1524-7zbMATH Open1327.05195arXiv1412.0130OpenAlexW2150681890MaRDI QIDQ897269FDOQ897269

Authors: Guantao Chen, Songling Shan 

Publication date: 17 December 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The square of a graph is obtained by adding additional edges joining all pair of vertices of distance two in the original graph. Particularly, if $C$ is a hamiltonian cycle of a graph $G$, then the square of $C$ is called a hamiltonian square of $G$. In this paper, we characterize all possible forbidden pairs, which implies the containment of a hamiltonian square, in a 4-connected graph. The connectivity condition is necessary as, except $K_3$ and $K_4$, the square of a cycle is always 4-connected.

Full work available at URL: https://arxiv.org/abs/1412.0130

Recommendations

• Characterizing forbidden pairs for hamiltonian properties
• Forbidden subgraphs and hamiitonian properties in the square of a connected graph
• Forbidden pairs for \(k\)-connected Hamiltonian graphs
• Extremal problems for forbidden pairs that imply hamiltonicity
• scientific article; zbMATH DE number 1161312
• Forbidden triples for Hamiltonicity
• Closure and forbidden pairs for Hamiltonicity
• On forbidden pairs implying Hamilton-connectedness
• Forbidden subgraphs for a graph to have a Hamiltonian path square
• Publication:4729825

zbMATH Keywords

forbidden pairHamiltonian square

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• Characterizing forbidden pairs for hamiltonian properties
• The square of paths and cycles
• Hamiltonian square-paths
• The Square of a Hamiltonian Cycle
• On the square of a Hamiltonian cycle in dense graphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Title not available (Why is that?)
• Pancyclicity of 4-connected \{claw, generalized bull\}-free graphs
• Pancyclicity of 4‐Connected, Claw‐Free, P₁₀‐Free Graphs

Cited In (7)

• Forbidden triples for Hamiltonicity
• Title not available (Why is that?)
• Closure and forbidden pairs for Hamiltonicity
• Title not available (Why is that?)
• Forbidden subgraphs for a graph to have a Hamiltonian path square
• Connectedness and acyclicity of the transposed square of a graph
• Hamiltonian cycles in the square of a graph

This page was built for publication: Characterizing forbidden pairs for Hamiltonian squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897269)