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 P and a graph G, the deficiency def(G) of the graph G with respect to the property P is the smallest non-negative integer t such that the join G∗Kt has property P . In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph G needs to ensure G∗Kt contains a Kr -factor (for any fixed r≥3 ). In this paper, we resolve their problem fully. We also give an analogous result that forces G∗Kt to contain any fixed bipartite (n+t) -vertex graph of bounded degree and small bandwidth.
Original language | English |
---|---|
Pages (from-to) | 478-488 |
Number of pages | 11 |
Journal | Combinatorics, Probability and Computing |
Volume | 31 |
Issue number | 3 |
Early online date | 27 Sept 2021 |
DOIs | |
Publication status | Published - May 2022 |
Bibliographical note
Funding Information:The authors are grateful to the referee for a helpful and careful review. Joseph Hyde was supported by the UK Research and Innovation Future Leaders Fellowship MR/S016325/1.
Publisher Copyright:
© The Author(s), 2021. Published by Cambridge University Press.
Keywords
- graph deficiency
- clique factors
- bandwidth theorems
ASJC Scopus subject areas
- Theoretical Computer Science
- Applied Mathematics
- Statistics and Probability
- Computational Theory and Mathematics