A generalization of Bondy's and Fan's sufficient conditions for Hamiltonian graphs
type: Item
instance of: scholarly article
title: A generalization of Bondy's and Fan's sufficient conditions for Hamiltonian graphs
zbMATH Open document ID: 0876.05061
DOI: 10.1016/0012-365X(95)00323-O
author: O. Diekmann
published in: Discrete Mathematics
publication date: 1997-11-04T00:00:00Z
review text: Chen et al. (1994) showed that for a \(k\)-connected graph \(G\) on \(n \geq 3\) vertices, if the maximum degree in any ``essential'' (i.e., containing two vertices a distance 2 apart) independent set of \(k\) vertices is at least \(n/2\), then \(G\) is Hamiltonian. The authors of this paper generalize the above result (and previous results of Fan and Bondy) by showing that for such \(G\), if the previous degree condition holds for any essential independent set on \(k+1\) vertices, then either \(G\) is Hamiltonian or is one of three types of graphs.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1021693
zbMATH Keywords: Hamiltonian graph
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q4192100
cites work: Q5422499
cites work: Essential independent sets and Hamiltonian cycles
cites work: A note on Hamiltonian circuits
cites work: New sufficient conditions for cycles in graphs
cites work: Note on Hamilton Circuits
full work available at URL: 0012-365x(95)00323-o
OpenAlex ID: W2045152458
description: scientific article; zbMATH DE number 1021693