Long cycles in graphs containing a 2-factor with many odd components
type: Item
instance of: scholarly article
title: Long cycles in graphs containing a 2-factor with many odd components
zbMATH Open document ID: 0822.05041
DOI: 10.1016/0012-365X(93)E0118-N
published in: Discrete Mathematics
publication date: 1995-10-05T00:00:00Z
review text: Let \(\sigma_ k(G)\) denote the minimum sum of the degrees of any \(k\) independent vertices of \(G\). It is shown that if \(G\) is a 2-connected graph of order \(n\) that contains a 2-factor with at least \(k\) odd components, and if \(\sigma_ 3(G)\geq n+ 2\), then \(G\) contains a cycle of length at least \(\min\{n, \sigma(G)/3+ n/2+ k/2\}\). There are several consequences of this theorem, one of which is a positive solution to a conjecture of Häggkvist that if \(G\) is a 2-connected graph of order \(n\) that has a 2-factor with at least \(k- 1\) odd components (actually \(2k\) components in the conjecture) and \(\sigma_ 2(G)\geq n- k\), then \(G\) is hamiltonian.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 719482
zbMATH Keywords: long cycles
zbMATH Keywords: independent vertices
zbMATH Keywords: 2-connected graph
zbMATH Keywords: 2-factor
zbMATH Keywords: odd components
zbMATH Keywords: conjecture of Häggkvist
zbMATH Keywords: hamiltonian
author: Jan van den Heuvel
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Q3971997
cites work: Long cycles in graphs with large degree sums
cites work: Q4192100
cites work: Q5422499
cites work: Degree sums, \(k\)-factors and Hamilton cycles in graphs
Wikidata QID: Q127773978
description: scientific article; zbMATH DE number 719482