Metraipolis › archive › dc_c281b2c3ee2b
The size and structure of graphs with a unique $k$-factor — arXiv:2611.00950
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00950
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:49:34.855Z
- SHA-256 of the archived text
7011ba71a4cfe83a2c87eb55f8e0fd2f290eddbbbb1eb08f184c566a9ff3e3b3- Stable URL of this page
https://metraipolis.com/documento/dc_c281b2c3ee2b
How to cite
The size and structure of graphs with a unique $k$-factor — arXiv:2611.00950 — arXiv (en), https://arxiv.org/abs/2611.00950 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c281b2c3ee2b (Metraipolis archive dc_c281b2c3ee2b, sha256 7011ba71a4cfe83a2c87eb55f8e0fd2f290eddbbbb1eb08f184c566a9ff3e3b3)
BibTeX
@misc{dcc281b2c3ee2b,
title = {The size and structure of graphs with a unique $k$-factor — arXiv:2611.00950},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00950},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c281b2c3ee2b; sha256 7011ba71a4cfe83a2c87eb55f8e0fd2f290eddbbbb1eb08f184c566a9ff3e3b3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00950. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For integers $n>k\ge1$ with $nk$ even, let $m(n,k)$ be the maximum size of a graph of order $n$ with a unique $k$-factor. In 1964, Hetyei and in 1984, Hendry [\emph{J. Combin. Theory Ser. B} \textbf{37} (1984), 53--63] proved $m(n,1)=n^2/4$ for even $n$ and $m(n,2)=\lfloor n(n+1)/4\rfloor$, respectively. In 2000, Johann [\emph{J. Graph Theory} \textbf{35} (2000), 227--243] showed that $m(n,k)=nk/2+\binom{n-k}{2}$ for $k>n/2$ and $kn$ even and $m(n,k)=n^2/4+(k-1)n/4$ for $n=2kq$, where $q$ is a positive integer. Later, Volkmann [\emph{Combinatorica} \textbf{24} (2004), 531--540] proved $m(n,k)=k^2+\binom{n-k}{2}$ for $n/3\le k<n/2$ and $kn$ even, and he determined $m(n,3)$. In this paper, we determine $m(n,k)$ for all admissible pairs, proving the size conjecture posed by Volkmann. We also prove that every extremal graph with $2\le k\le n-2$ has a universal vertex whose neighbors in the unique factor are precisely its degree-$k$ vertices. In particular, this result confirms Volkmann's structural conjecture.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.00950 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:38.056Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).