Hamiltonian square-paths

Genghua Fan, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


A hamiltonian square-path (-cycle) is one obtained from a hamiltonian path (cycle) by joining every pair of vertices of distance two in the path (cycle). Let G be a graph on n vertices with minimum degree δ(G). Posá and Seymour conjectured that if δ(G) ≥ 2/3n, then G contains a hamiltonian square-cycle. We prove that if δ(G) ≥ (2n - 1)/3, then G contains a hamiltonian square-path. A consequence of this result is a theorem of Aigner and Brandt that confirms the case △(H) = 2 of the Bollabás-Eldridge Conjecture: if G and H are graphs on n vertices and (△(G) + 1)(△(H) + 1) ≤ n + 1, then G and H can be packed.

Original languageEnglish (US)
Pages (from-to)167-182
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Issue number2
StatePublished - Jul 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Hamiltonian square-paths'. Together they form a unique fingerprint.

Cite this