Square Hamiltonian cycles in graphs with maximal 4-cliques
type: Item
instance of: scholarly article
title: Square Hamiltonian cycles in graphs with maximal 4-cliques
zbMATH Open document ID: 0890.05045
DOI: 10.1016/S0012-365X(97)81819-5
author: Juan Quintana
author: H. A. Kierstead
published in: Discrete Mathematics
publication date: 1998-06-22T00:00:00Z
review text: Seymour conjectured that if \(G\) is a graph of order \(n\) with minimum degree at least \(kn/(k+1)\), then \(G\) contains the \(k\)th power of a Hamiltonian cycle. The special case when \(k = 2\) was conjectured earlier by Pósa. In the case when the graph \(G\) contains a maximal \(4\)-clique, the conjecture of Pósa is verified (e.g. if \(G\) has minimal degree at least \(2n/3\) and a maximal \(4\)-clique, then \(G\) has the square of a Hamiltonian cycle). An asymptotic version of the conjecture of Pósa has been proved by Komol'os, Sárkőzy, and Szemerédi, but is not yet in print.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1110096
zbMATH Keywords: Hamiltonian square
zbMATH Keywords: degree condition
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Some Theorems on Abstract Graphs
cites work: The Square of a Hamiltonian Cycle
cites work: The square of paths and cycles
cites work: Hamiltonian square-paths
cites work: Partitioning a graph into two square-cycles
cites work: On the square of a Hamiltonian cycle in dense graphs
cites work: Q4766926
full work available at URL: s0012-365x(97)81819-5
OpenAlex ID: W2037778884
description: scientific article; zbMATH DE number 1110096