Kr-Packings in Graphs with tr−1(n)+k Edges
Abstract
Fix an integer r≥ 3. Let Kr denote the complete graph on r vertices and tr−1(n) the Turán number for Kr. For each integer k satisfying 0≤ k ≤ binomn2−tr−1(n), revϕr(n,k) denotes the minimum, over all n-vertex graphs with tr−1(n)+k edges, of the maximum size of a Kr-packing \rev{(a family of edge-disjoint copies of Kr)} in the graph. The problem of characterizing the behavior of ϕr(n,k) has a long history and dates back to Erdős for the case r=3. \rev{Győri} proved that ϕr(n,k)=(1−o(1))k whenever k=o(n2). We characterize the range of k for which ϕr(n,k)=(1−o(1))k, showing that this equality holds if and only if k=o(n2). Moreover, we obtain an \rev{asymptotic} upper bound (which falls below $1$) for ϕr(n,k)/k whenever k/n2 converges to a constant δ satisfying 0 < δ≤ 1/(2(r−1)).
Related
- On the number of edges in quasiplanar graphs
- The maximum number of edges in minimal matching covered graphs
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
- Four triangle-free intrinsically knotted graphs with 22 edges
- On rainbow saturated graphs with minimum number of edges
BibTeX
@misc{bai2026krpackings,
title = {{$K_r$-Packings in Graphs with $t_r-1(n)+k$ Edges}},
author = {Hanzhi Bai and Fuhong Ma and Jin Yan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41371},
eprint = {2610.41371},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41371},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - K_r-Packings in Graphs with t_r−1(n)+k Edges
AU - Hanzhi Bai
AU - Fuhong Ma
AU - Jin Yan
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41371
UR - https://arxiv.org/abs/2610.41371
AB - Fix an integer r≥ 3. Let K_r denote the complete graph on r vertices and t_r−1(n) the Turán number for K_r. For each integer k satisfying 0≤ k ≤ binomn2−t_r−1(n), revϕ_r(n,k) denotes the minimum, over all n-vertex graphs with t_r−1(n)+k edges, of the maximum size of a K_r-packing \rev{(a family of edge-disjoint copies of K_r)} in the graph. The problem of characterizing the behavior of ϕ_r(n,k) has a long history and dates back to Erdős for the case r=3. \rev{Győri} proved that ϕ_r(n,k)=(1−o(1))k whenever k=o(n^2). We characterize the range of k for which ϕ_r(n,k)=(1−o(1))k, showing that this equality holds if and only if k=o(n^2). Moreover, we obtain an \rev{asymptotic} upper bound (which falls below $1$) for ϕ_r(n,k)/k whenever k/n^2 converges to a constant δ satisfying 0 < δ≤ 1/(2(r−1)).
ER -