Characterizing forbidden pairs for hamiltonian squares

2014/11/29 by Guantao Chen, Songling Shan, Chen, Guantao +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1412.0130

arxiv created 2014/11/29 · openalex publication_date 2014/11/29 · arxiv updated 2014/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₃ and K₄, the square of a cycle is always 4-connected.

Related

• Revisiting the Hamiltonian Theme in the Square of a Block: The Case of\n DT-Graphs
• Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles
• A Best Possible Result for the Square of a 2-Block to be Hamiltonian
• Revisiting the Hamiltonian Theme in the Square of a Block: The General\n Case
• Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian