On unique k-factors and unique [1,k]-factors in graphs.

DOI10.1016/S0012-365X(03)00248-6MaRDI QIDQ1427474zbMATH OpenFDO

Authors Arne Hoffmann, Lutz Volkmann

Publication date 14 March 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(03)00248-6

zbMATH Keywords

\([1\(k\)-factorextremal graphsk\)-factor]

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• On the structure of graphs having a unique \(k\)-factor
• On the structure of graphs with a uniquek-factor
• On the structure of graphs with a unique \(k\)-factor
• scientific article; zbMATH DE number 2192138
• scientific article; zbMATH DE number 3961661
• A note concerning graphs with unique f-factors
• scientific article; zbMATH DE number 7448387
• On uniqueness of a general factorization of graph properties
• Structural remarks on bipartite graphs with unique \(f\)-factors
• On uniqueness of prime bipartite factors of graphs

Cites work

• 1-Faktoren von Graphen. (1-factors of graphs)
• A note concerning graphs with unique f-factors
• Graphs with exactly one hamiltonian circuit
• scientific article; zbMATH DE number 3150487 (Why is no real title available?)
• scientific article; zbMATH DE number 843316 (Why is no real title available?)
• Maximum graphs with a unique k-factor
• On the 1-factors of a non-separable graph
• On the structure of factorizable graphs
• On the structure of graphs with a uniquek-factor
• The 1-Factors of Oriented Graphs
• The maximum size of graphs with a unique \(k\)-factor

Cited in

(16)

• Counting 1-factors in regular bipartite graphs
• Structural remarks on bipartite graphs with unique \(f\)-factors
• A note concerning graphs with unique f-factors
• Extremal bipartite graphs with a unique k-factor
• scientific article; zbMATH DE number 3961661 (Why is no real title available?)
• scientific article; zbMATH DE number 4101257 (Why is no real title available?)
• On the maximum number of edges in a hypergraph with a unique perfect matching
• On the size and structure of graphs with a constant number of 1-factors
• On the structure of graphs with a uniquek-factor
• On the structure of graphs having a unique \(k\)-factor
• On graphs with a unique perfect matching
• scientific article; zbMATH DE number 4185653 (Why is no real title available?)
• On graphs that contain exactly \(k\) copies of a subgraph, and a related problem in search theory
• Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
• Graph factors and factorization: 1985--2003: a survey
• Graphs with the maximum or minimum number of 1-factors

This page was built for publication: On unique \(k\)-factors and unique \([1,k]\)-factors in graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1427474)