The size and structure of graphs with a unique k-factor

Abstract

For integers n>k≥1 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²/4 for even n and m(n,2)=⌊ n(n+1)/4⌋, respectively. In 2000, Johann [\emph{J. Graph Theory} \textbf{35} (2000), 227--243] showed that m(n,k)=nk/2+binomn−k2 for k>n/2 and kn even and m(n,k)=n²/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²+binomn−k2 for n/3≤ 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≤ k≤ 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.

Spectral radius and size conditions for 1-tough balanced bipartite graphs to contain a k-factor with k≥ 3
Jinxuan Ren, Jiayao Song, Ligong Wang
arXiv2 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Size and spectral radius conditions for the existence of k-factor in graphs with given minimum degree
Zengzhao Xu, Bo Deng, Ligong Wang
arXiv20 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Chains and unique transitive orientations of prime graphs
Robert Brignall, Sean Mandrick, Vincent Vatter
arXiv7 Sep 2026PreprintCC0Full textCombinatorics & discrete mathematicsarXiv
A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
Adam Y. Shavit
arXiv20 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A two-dimensional subspace of ℓ_∞³ has a unique operator space structure if and only if it is isometric to ℓ_∞²
Rajeev Gupta, Arpita Mal, Gadadhar Misra +1
arXiv19 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{yang2026size,
  title = {{The size and structure of graphs with a unique $k$-factor}},
  author = {Zixuan Yang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00950},
  eprint = {2611.00950},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00950},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - The size and structure of graphs with a unique k-factor
AU  - Zixuan Yang
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00950
UR  - https://arxiv.org/abs/2611.00950
AB  - For integers n>k≥1 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)=⌊ n(n+1)/4⌋, respectively. In 2000, Johann [\emph{J. Graph Theory} \textbf{35} (2000), 227--243] showed that m(n,k)=nk/2+binomn−k2 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+binomn−k2 for n/3≤ 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≤ k≤ 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.
ER  -

Abstract

Related

Cite