Toughness, degrees and 2-factors
type: Item
instance of: scholarly article
title: Toughness, degrees and 2-factors
zbMATH Open document ID: 1060.05056
author: Akira Saito
author: Ralph Faudree
author: Ronald Gould
author: Michael Jacobson
author: Linda Lesniak
published in: Discrete Mathematics
publication date: 2004-11-22T00:00:00Z
review text: A \(2\)-factor of a graph is a \(2\)-regular spanning subgraph, i.e., the disjoint union of cycles that span the vertex set of the graph. The note under review discusses necessary conditions on a graph of order \(n\) such that it has \(2\)-factors with \(k\) cycles for \(1\leq k\leq C(n)\) and some constant \(C(n)\). The authors prove: If \(G\) is disconnected, \(n\geq 8\), and the minimum degree is at least \((n-4)/2\), then \(G\) contains a \(2\)-factor with \(k\) cycles for \(2\leq k\leq \lceil (n-4)/3\rceil\). If \(G\) is connected, \(n\geq 8\), \(G\) is not \(1\)-tough, and the minimum degree is at least \((n-4)/2\), then \(G\) contains a \(2\)-factor with \(k\) cycles for \(2\leq k\leq \lceil (n-4)/3\rceil\). Finally, if \(G\) is \(1\)-tough (i.e., \(G-S\) has at most \(| S| \) components for all nonempty subsets \(S\) of the vertex set), \(n\) is sufficiently large, and the minimum degree is at least \((n-t)/2\) for some \(0\leq t\leq 4\), then \(G\) contains a \(2\)-factor with \(k\) cycles where \(1\leq k\leq n/4-t\).
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 2117316
zbMATH Keywords: toughness
zbMATH Keywords: 2-Factor, cycle
zbMATH Keywords: Degrees
zbMATH Keywords: Hamiltonian graphs
MaRDI profile type: Publication
full work available at URL: j.disc.2004.05.008
OpenAlex ID: W2067068600
cites work: Embedding Arbitrary Graphs of Maximum Degree Two
cites work: Degree conditions for 2-factors
cites work: Some Theorems on Abstract Graphs
cites work: Cycles in 2-factors of balanced bipartite graphs
cites work: On Maximal Circuits in Finite Graphs
cites work: Edge disjoint placement of graphs
DOI: 10.1016/J.DISC.2004.05.008
description: scientific article; zbMATH DE number 2117316