Pancyclism in Chvátal-Erdős' graphs
type: Item
instance of: scholarly article
title: Pancyclism in Chvátal-Erdős' graphs
zbMATH Open document ID: 0732.05034
DOI: 10.1007/BF01788136
published in: Graphs and Combinatorics
publication date: 1991-01-01T00:00:00Z
review text: Let G be a simple graph with stability number \(\alpha\) and connectivity k such that \(\alpha\leq k\). According to a theorem by Chvátal-Erdős, G has a Hamiltonian cycle. This paper gives results about cycles of other lengths for such G. For example: (1) If \(G\neq K_{k,k}\) and \(G\neq C_ 5\), then G has a \(C_{n-1}.\) (2) If \(G\not\cong C_ 5\), then G has a \(C_ 4.\) (3) If \(\alpha =3\) and if \(G\neq K_{3,3}\), G has cycles of any length between 4 and n. The authors conjecture that the conclusion of (3) holds more generally when \(\alpha\leq k\) and G is not bipartite.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4210174
zbMATH Keywords: pancyclic graph
author: Denise Amar
author: Irene Fournier
author: Anne Germa
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: A note on Hamiltonian circuits
cites work: Applications of Menger's graph theorem
full work available at URL: https://doi.org/10.1007/bf01788136
OpenAlex ID: W2030170217
description: scientific article; zbMATH DE number 4210174