The maximum size of graphs with a unique k-factor

DOI10.1007/S00493-004-0032-9MaRDI QIDQ705753zbMATH OpenOpenAlexFDO

Publication date 14 February 2005

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-004-0032-9

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

Review text

For positive integers \(k\) and \(n\), \(k< n\), \(kn\) even, let \(m(n,k)\) be the maximum number of edges in a graph of order \(n\) that contains a unique \(k\)-factor. The author proves \(m(n,k)=k^2+{n-k\choose 2}\) for values of \(n\) and \(k\) with \(5\leq 2k+1\leq n\leq 3k\). Furthermore, he extends results due to \textit{G. Hetyei} (see \textit{L. Lovász} [Acta Math. Acad. Sci. Hung. 23, 223--246 (1972; Zbl 0247.05155)]) and \textit{G. R. T. Hendry} [J. Comb. Theory, Ser. B 37, 53--63 (1984; Zbl 0535.05036)] about \(m(n,1)\) and \(m(n,2)\) by proving that \(m(n,3)=\frac{n^2}{4}+\frac{n}{2}\) for \(n\geq 4\) with \(n\equiv 0,4 \pmod{6}\), \(m(n,3)=\frac{n^2}{4}+\frac{n}{2}-1\) for \(n\geq 4\) with \(n\equiv 2\pmod{6}\). The author closes with two conjectures one of which states that every graph of order \(n\) that has a unique \(k\)-factor for some \(2\leq k\leq n-2\) and is of maximum size contains exactly \(k\) vertices of degree \(k\) which generalizes results due to \textit{B. Jackson} and \textit{R. W. Whitty} [J. Graph Theory 13, 577--580 (1989; Zbl 0962.05050)].

Recommendations

Cited in

(12)

This page was built for publication: The maximum size of graphs with a unique \(k\)-factor

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