On deficiency problems for graphs

Abstract

Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property $\mathcal{P}$ and a graph $G$, the deficiency $\text{def}(G)$ of the graph $G$ with respect to the property $\mathcal{P}$ is the smallest non-negative integer $t$ such that the join $G\ast K_t$ has property $\mathcal{P}$. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an $n$-vertex graph $G$ needs to ensure $G\ast K_t$ contains a $K_r$-factor (for any fixed $r\ge 3$). In this paper we resolve their problem fully. We also give an analogous result which forces $G\ast K_t$ to contain any fixed bipartite $(n+t)$-vertex graph of bounded degree and small bandwidth.

12 pages, author accepted manuscript, to appear in Combinatorics, Probability and Computing