On unique \(k\)-factors and unique \([1,k]\)-factors in graphs.
type: Item
instance of: scholarly article
title: On unique \(k\)-factors and unique \([1,k]\)-factors in graphs.
zbMATH Open document ID: 1041.05060
DOI: 10.1016/S0012-365X(03)00248-6
author: Arne Hoffmann
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2004-03-14T00:00:00Z
review text: Let \(G\) be a graph and let \(a\) and \(b\), \(a\leq b\), be two positive integers. A spanning subgraph \(F\) of \(G\) is an \([a,b]\)-factor if \(a\leq \deg_Fv\leq b\), for every vertex \(v\) in \(G\). A \([k,k]\)-factor is called a \(k\)-factor. An \([a,b]\)-factor is perfect if each of its components is a regular graph. The authors give upper bounds (in terms of \(n\) and \(k\)) on the number of edges in a bipartite graph of an even order \(n\) which has a unique \(k\)-factor. In the case of \(k=3\), they give a sharp upper bound. Moreover, they show an upper bound (in terms of \(n\) and \(k\)) for the number of edges in a graph of order \(n\) with a unique \([1,k]\)-factor. The bound is tight. Finally, the authors prove an upper bound for the number of edges in a graph of order \(n\) with a unique perfect \([1,2]\)-factor and observe that if a graph has a unique perfect \([1,k]\)-factor then the factor has to be a perfect \([1,2]\)-factor.
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 2055736
zbMATH Keywords: \(k\)-factor
zbMATH Keywords: \([1
zbMATH Keywords: k]\)-factor
zbMATH Keywords: extremal graphs
MaRDI profile type: Publication
cites work: On the 1-factors of a non-separable graph
cites work: Maximum graphs with a unique k-factor
cites work: A note concerning graphs with unique f-factors
cites work: On the structure of graphs with a uniquek-factor
cites work: Q3267903
cites work: On the structure of factorizable graphs
cites work: 1-Faktoren von Graphen. (1-factors of graphs)
cites work: Graphs with exactly one hamiltonian circuit
cites work: The 1-Factors of Oriented Graphs
cites work: Q4862678
cites work: The maximum size of graphs with a unique \(k\)-factor
Recommended article: Q4595639
Recommended article: On the structure of graphs with a uniquek-factor
Recommended article: On the structure of graphs with a unique \(k\)-factor
Recommended article: Q5463512
Recommended article: Q3728942
Recommended article: A note concerning graphs with unique f-factors
Recommended article: Q5016980
Recommended article: On uniqueness of a general factorization of graph properties
Recommended article: Structural remarks on bipartite graphs with unique \(f\)-factors
Recommended article: On uniqueness of prime bipartite factors of graphs
description: scientific article; zbMATH DE number 2055736