Hamiltonian cycles in regular graphs of moderate degree
type: Item
instance of: scholarly article
title: Hamiltonian cycles in regular graphs of moderate degree
zbMATH Open document ID: 0374.05037
DOI: 10.1016/0095-8956(77)90063-6
author: Arthur M. Hobbs
author: P. Erdős
published in: Journal of Combinatorial Theory. Series B
publication date: 1977-01-01T00:00:00Z
review text: It is shown that if \(k\) is an integer no less than 3, and if \(G\) is a 2-connected graph with \(2n-a\) vertices, \(a\in\{0,1\}\), which is regular of degree \(n-k\), then \(G\) is Hamiltonian if \(a=0\) and \(n\geq k^2+k+1\) or if \(a=1\) and \(n\geq 2k^2-3k+3\). Subsequently, \textit{B.Bollobás} and \textit{A.M.Hobbs} have proved a stronger result in [Ann. Discrete Math. 3, 43-49 (1978; Zbl 0376.05036)] , and more recently, \textit{W.Jackson} has obtained the best possible result that a 2-connected \(k\)-regular graph with at most \(3k\) vertices is Hamiltonian [J. Comb. Theory, Ser. B 29, 27-46 (1980; Zbl 0432.05037)] .
reviewed by: Carsten Thomassen
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3582186
MaRDI profile type: Publication
full work available at URL: 0095-8956(77)90063-6
OpenAlex ID: W2170981445
cites work: Q5648381
cites work: Some Theorems on Abstract Graphs
cites work: A class of Hamiltonian regular graphs
description: scientific article; zbMATH DE number 3582186