On unique \(k\)-factors and unique \([1,k]\)-factors in graphs. (Q1427474): Difference between revisions

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.