On the odd independence number of the Queen graph

Martin Knor, Jelena Sedlar, Riste Škrekovski

arXiv:2608.19024v1 Primary: math.CO

Abstract

A set S of vertices of a graph is odd independent if it is independent and every vertex outside S has either zero or an odd number of neighbors in S. The largest size of such a set is the odd independence number alpha_od. Caro, Petrusevski, Skrekovski and Tuza [2] conjectured that alpha_od = 1 for every finite Queen graph. They also asked whether the infinite Queen graph has alpha_od = 1 or alpha_od = infinity. We prove that alpha_od = 1 in both cases. In particular, in the case of an infinite board we prove that alpha_od = 1 holds on the quarter plane and on the whole plane.

Disclosure

“ian Ministry of Science, Education and Youth through the bilateral Croatian-Slovenian project 2025- 26, and by the NextGeneration EU foundation via IP-UNIST-17 (GEORAZ). AI declaration. Results in this manuscript were obtained with help of Claude AI. References [1] Y. Caro, M. Petruševski, R. Škrekovski, Zs. Tuza, The odd independence number of graphs, I: Foundations and classical classes, arXiv:2509.20763, 2025. [2] Y. Caro, M. Petruševski, R. Škrekovski, Zs. Tuza, The”
PDF page 11

Classification: Substantial mathematical content or result generation
Multiplier: 10
Verified: 2026-08-22T18:21:26.180325Z

Structural counts

Pages 11 pdf

Theorems 2 source

Lemmas 5 source

Propositions 1 source

Corollaries 2 source

Definitions 0 source

Displayed equations 21 source

Bibliography entries 7 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file KingConjecture_v16.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.