Two sufficient conditions for Hamilton and dominating cycles
type: Item
instance of: scholarly article
title: Two sufficient conditions for Hamilton and dominating cycles
zbMATH Open document ID: 1257.05081
DOI: 10.1155/2012/185346
author: Zh. G. Nikoghosyan
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2013-02-21T00:00:00Z
review text: Summary: We prove that if \(G\) is a 2-connected graph of size \(q\) (the number of edges) and minimum degree \(\delta\) with \(\delta \geq \sqrt{2q/3 + \epsilon/12} - 1/2\), where \(\epsilon = 11\) when \(\delta = 2\) and \(\epsilon = 31\) when \(\delta \geq 3\), then each longest cycle in \(G\) is a dominating cycle. The exact analog of this theorem for Hamiltonian cycles follows easily from two known results according to Dirac and Nash-Williams: each graph with \(\delta \geq \sqrt{q + 5/4} - 1/2\) is Hamiltonian. Both results are sharp in all respects.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6137705
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/185346
OpenAlex ID: W2098163515
Wikidata QID: Q58705594
cites work: Q3097395
cites work: Some Theorems on Abstract Graphs
cites work: Q5628163
description: scientific article; zbMATH DE number 6137705