Characterizing forbidden pairs for Hamiltonian squares

DOI10.1007/S00373-015-1524-7MaRDI QIDQ897269zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Songling Shan

Publication date 17 December 2015

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

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

zbMATH Keywords

forbidden pairHamiltonian square

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• Characterizing forbidden pairs for hamiltonian properties
• Hamiltonian square-paths
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• On the square of a Hamiltonian cycle in dense graphs
• Pancyclicity of 4-connected \{claw, generalized bull\}-free graphs
• Pancyclicity of 4-connected, claw-free, \(P_{10}\)-free graphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• The Square of a Hamiltonian Cycle
• The square of paths and cycles

Cited in

(7)

• Connectedness and acyclicity of the transposed square of a graph
• Hamiltonian cycles in the square of a graph
• Forbidden triples for Hamiltonicity
• scientific article; zbMATH DE number 3867373 (Why is no real title available?)
• scientific article; zbMATH DE number 4089597 (Why is no real title available?)
• Forbidden subgraphs for a graph to have a Hamiltonian path square
• Closure and forbidden pairs for Hamiltonicity

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)