The square of paths and cycles

G. H. Fan, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


The square of a path (cycle) is the graph obtained 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á conjectured that if δ(G) ≥ 2 3n, then G contains the square of a hamiltonian cycle. This is also a special case-of a conjecture of Seymour. In this paper, we prove that for any ε > 0, there exists a number m, depending only on ε, such that if δ(G) ≥ (2/3 + ε) n + m, then G contains the square of a hamitonian path between any two edges, which implies the squares of a hamiltonian cycle.

Original languageEnglish (US)
Pages (from-to)55-64
Number of pages10
JournalJournal of Combinatorial Theory, Series B
Issue number1
StatePublished - Jan 1995

ASJC Scopus subject areas

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


Dive into the research topics of 'The square of paths and cycles'. Together they form a unique fingerprint.

Cite this