Degree conditions for Hamiltonicity: counting the number of missing edges
type: Item
instance of: scholarly article
title: Degree conditions for Hamiltonicity: counting the number of missing edges
zbMATH Open document ID: 1122.05055
author: R. H. Schelp
author: Akira Saito
author: Ingo Schiermeyer
author: Ralph Faudree
published in: Discrete Mathematics
publication date: 2007-03-02T00:00:00Z
review text: Dirac showed that if \(G\) is a graph of order \(n\) having minimum degree at least \(n/2\), then \(G\) is Hamiltonian. Ore strengthened this result by showing that if the sum of the degrees of every pair of non-adjacent vertices is at least \(n\), then \(G\) is Hamiltonian. Fan showed that if \(G\) is a 2-connected graphs of order \(n\) such that \(\max\{d(u), d(v)\} \geq n/2\) for every pair \(u,v\) of vertices distance \(2\) apart, then \(G\) is Hamiltonian. The authors strengthen each of these results by showing that if the conditions are not violated too often, then \(G\) is still guaranteed to be Hamiltonian. In particular they show that if \(G\) is a graph of order \(n\) and minimum degree \(\delta < n/2\) having at most \(\delta -1\) vertices of degree less than \(n/2\), then \(G\) is Hamiltonian. Similar improvements for Ore and Fan's results are given. They also show that their results are best possible.
reviewed by: Ortrud R. Oellermann
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5130445
zbMATH Keywords: Hamiltonian graph
zbMATH Keywords: degree condition
MaRDI profile type: Publication
full work available at URL: j.disc.2005.11.037
OpenAlex ID: W1996647345
cites work: A remark on two sufficient conditions for Hamilton cycles
cites work: A method in graph theory
cites work: Q5422499
cites work: Q4350166
cites work: A note on Hamiltonian circuits
cites work: Some Theorems on Abstract Graphs
cites work: Q5722820
cites work: New sufficient conditions for cycles in graphs
cites work: Some recent results in hamiltonian graphs
cites work: Decomposition of Finite Graphs into Open Chains
cites work: Note on Hamilton Circuits
cites work: Q5722819
cites work: Q5599564
cites work: Q3201098
DOI: 10.1016/J.DISC.2005.11.037
description: scientific article; zbMATH DE number 5130445