Odd covers of complete graphs and hypergraphs
Document Type
Article
Publication Date
2-1-2026
Abstract
The ‘odd cover number’ of a complete graph is the smallest size of a family of complete bipartite graphs that covers each edge an odd number of times. For n odd, Buchanan, Clifton, Culver, Nie, O’Neill, Rombach and Yin showed that the odd cover number of Kn is equal to (n+1)/2 or (n+3)/2, and they conjectured that it is always (n+1)/2. We prove this conjecture. For n even, Babai and Frankl showed that the odd cover number of Kn is always at least n/2, and the above authors and Radhakrishnan, Sen and Vishwanathan gave some values of n for which equality holds. We give some new examples. Our constructions arise from some very symmetric constructions for the corresponding problem for complete hypergraphs. That is, the odd cover number of the complete 3-graph Kn (3) is the smallest number of complete 3-partite 3-graphs such that each 3-set is in an odd number of them. We show that the odd cover number of Kn (3) is exactly n/2 for even n, and we show that for odd n it is (n−1)/2 for infinitely many values of n. We also show that for r=3 and r=4, the odd cover number of Kn (r) is strictly less than the partition number, answering a question of Buchanan, Clifton, Culver, Nie, O’Neill, Rombach and Yin for those values of r.
Publication Title
European Journal of Combinatorics
ISSN
0195-6698
DOI
10.1016/j.ejc.2025.104299
Recommended Citation
Leader, Imre and Tan, Ta Sheng, "Odd covers of complete graphs and hypergraphs" (2026). Research Publications (2026 to 2030). 1303.
https://knova.um.edu.my/research_publications_2026_2030/1303
Volume
132
Publisher
Academic Press