Spectral Extremal Graphs without a K_k-Factor

Abstract

Let k≥ 3 and let n=km. A K_k-factor in an n-vertex graph is a collection of m vertex-disjoint copies of K_k that covers the entire vertex set. We determine the maximum adjacency spectral radius of an n-vertex graph containing no K_k-factor when m≥ 2k−1. More precisely, we prove that every such graph G satisfies ρ(G)≤ ρ(H_n,k), H_n,k=K_k−2∨(K_n−k+1∪ K₁), with equality if and only if G≅ H_n,k. Equivalently, the unique extremal graph is obtained from K_n−1 by adding one vertex adjacent to exactly k−2 vertices of the clique. Our proof combines a decomposition lemma for sparse complements, derived from the Hajnal--Szemerédi theorem, with the Motzkin--Straus inequality and spectral estimates based on quotient matrices and the Rayleigh quotient.

Extremal spectral result of outerplanar graphs without P_{3· l}
Fulong Ye, Yuxiang Liu, Ligong Wang
arXiv21 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Spectral extremal problems on 1-planar graphs without Friendship graph
Jiamin Li, Dan Li, Yuanyuan Chen
arXiv6 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Extremal graphs without cycles of length 0 modulo 4
Yanan Hu, Leilei Zhang
arXiv20 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
Zejun Huang, Chenxi Yang
arXiv22 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Spectral extremal hypergraphs without long Berge cycles
Lihua Feng, Lu Lu, Tingzeng Wu
arXiv1 Sep 2026PreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{duan2026spectral,
  title = {{Spectral Extremal Graphs without a $K_k$-Factor}},
  author = {Cunxiang Duan and Tingting Han and Lin-Peng Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.21529},
  eprint = {2609.21529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21529},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Spectral Extremal Graphs without a K_k-Factor
AU  - Cunxiang Duan
AU  - Tingting Han
AU  - Lin-Peng Zhang
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.21529
UR  - https://arxiv.org/abs/2609.21529
AB  - Let k≥ 3 and let n=km. A K_k-factor in an n-vertex graph is a collection of m vertex-disjoint copies of K_k that covers the entire vertex set. We determine the maximum adjacency spectral radius of an n-vertex graph containing no K_k-factor when m≥ 2k−1. More precisely, we prove that every such graph G satisfies ρ(G)≤ ρ(H_n,k), H_n,k=K_k−2∨(K_n−k+1∪ K_1), with equality if and only if G≅ H_n,k. Equivalently, the unique extremal graph is obtained from K_n−1 by adding one vertex adjacent to exactly k−2 vertices of the clique. Our proof combines a decomposition lemma for sparse complements, derived from the Hajnal--Szemerédi theorem, with the Motzkin--Straus inequality and spectral estimates based on quotient matrices and the Rayleigh quotient.
ER  -

Abstract

Related

Cite