Extensions and consequences of Chvátal-Erdös' theorem
type: Item
instance of: scholarly article
title: Extensions and consequences of Chvátal-Erdös' theorem
zbMATH Open document ID: 0858.05069
DOI: 10.1007/BF01858457
published in: Graphs and Combinatorics
publication date: 1997-03-11T00:00:00Z
review text: A well-known result of Chvátal and Erdös states that if \(G\) is a graph with at least 3 vertices such that \(\alpha(G)\leq \kappa(G)\), then \(G\) is hamiltonian. An ascending chain of generalizations of this result is given terminating with the following result. If \(G\) is a connected graph on at least 3 vertices such that for every connected subgraph \(H\) of \(G\) with \(N_2(H)\neq\varnothing\) (where \(N_2(H)\) is the set of vertices at a distance 2 from \(H\)) there does not exist an independent set \(S\) in \(N_2(H)\) and a matching \(M\) in \(G\) with \(|S|=|M|=|N(H)|\) and such that \(V(M)=S\cup N(H)\), then \(G\) is hamiltonian. Other well-known hamiltonian results, for example the theorem of Ore, are consequences of this generalization.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 934036
zbMATH Keywords: neighborhood
zbMATH Keywords: hamiltonian
zbMATH Keywords: theorem of Ore
author: Jan van den Heuvel
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: On graphs satisfying a local ore-type condition
cites work: A remark on two sufficient conditions for Hamilton cycles
cites work: Q3097395
cites work: A note on Hamiltonian circuits
cites work: Some localization theorems on Hamiltonian circuits
cites work: A chvátal–erdős type condition for hamiltonian graphs
cites work: Note on Hamilton Circuits
cites work: 2‐neighborhoods and hamiltonian conditions
cites work: Existence of Dlambda-cycles and Dlambda-paths
full work available at URL: https://doi.org/10.1007/bf01858457
OpenAlex ID: W2097294316
description: scientific article; zbMATH DE number 934036