The square of paths and cycles
type: Item
instance of: scholarly article
title: The square of paths and cycles
zbMATH Open document ID: 0826.05040
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-02T00:00:00Z
review text: The square of a cycle (path) is the graph obtained by joining every pair of vertices of distance two in the cycle (path). Posa conjectured that if a graph \(G\) on \(n\) vertices has minimum degree \(\delta(G)\) at least \({2\over 3}n\), then \(G\) contains the square of a Hamiltonian cycle. The main result shown here is the following: Let \(G\) be a graph on \(n\) vertices. For any \(\varepsilon> 0\), there exists a number \(m\), depending only on \(\varepsilon\), such that if \(\delta(G)\geq ({2\over 3}+ \varepsilon) n+ m\), then any two independent edges in \(G\) are joined by the square of a Hamiltonian path in \(G\). Consequently, such \(G\) contains the square of a Hamiltonian cycle. The proof uses a lemma of Häggkvist on 3-partitioning the vertices of a graph.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 767680
zbMATH Keywords: square of a path
zbMATH Keywords: square of a cycle
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: Hamiltonian path
author: Genghua Fan
author: H. A. Kierstead
MaRDI profile type: Publication
full work available at URL: jctb.1995.1005
OpenAlex ID: W2066235086
DOI: 10.1006/JCTB.1995.1005
description: scientific article; zbMATH DE number 767680