Dirac's minimum degree condition restricted to claws
type: Item
instance of: scholarly article
title: Dirac's minimum degree condition restricted to claws
zbMATH Open document ID: 0880.05062
DOI: 10.1016/S0012-365X(96)00224-5
author: Zdeněk Ryjáček
author: Hajo Broersma
author: Ingo Schiermeyer
published in: Discrete Mathematics
publication date: 1998-01-19T00:00:00Z
review text: A graph \(G\) of order \(n\) is 1-heavy (2-heavy) if at least one (two) of the end vertices of each induced claw \(K_{1,3}\) has degree at leat \(n/2\). It is shown that if \(G\) is a 2-connected 2-heavy graph of order \(n\geq 3\) such that \(|N(u)\cup N(v)|\geq 2\) for each pair of vertices \(u\) and \(v\) with \(d(u,v)=2\) and \(\max\{d(u),d(v)\}< n/2\), then \(G\) is Hamiltonian. This generalizes several known Hamiltonian results, including the result of Shi. Other forms of the result are also proved; for example, ``2-connected and 2-heavy'' can be replaced by ``3-connected and 1-heavy'' without changing the conclusion that the graph is Hamiltonian. Results on the relationship between the previously mentioned conditions and toughness and the existence of perfect matchings are also proved.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1018510
zbMATH Keywords: Dirac's minimum degree condition
zbMATH Keywords: claw
zbMATH Keywords: Hamiltonian
zbMATH Keywords: toughness
zbMATH Keywords: perfect matchings
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: A generalization of Fan's condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness
cites work: Cycles through specified vertices
cites work: Q4192100
cites work: A method in graph theory
cites work: Q5422499
cites work: Q3211339
cites work: A note on Hamiltonian circuits
cites work: Some Theorems on Abstract Graphs
cites work: New sufficient conditions for cycles in graphs
cites work: Q4862340
cites work: Sufficient conditions for a graph to be Hamiltonian
cites work: Q4074931
cites work: Hamiltonian results inK1,3-free graphs
cites work: Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
cites work: Note on Hamilton Circuits
cites work: 2‐neighborhoods and hamiltonian conditions
cites work: Graphs with 1-Factors
cites work: 1-Factors and Antifactor Sets
description: scientific article; zbMATH DE number 1018510