PreprintarXiv licencearXiv
On the odd independence number of the Queen graph
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.
Related
- On the Stability of the Independence Number of the Distance Graph G(n,r,<s) for Growing r and s
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- Strong complete immersions in graphs with independence number two
- Tree Independence Number III. Thetas, Prisms and Stars
- Connected graphs with equal independence number and radius
BibTeX
@misc{knor2026independence,
title = {{On the odd independence number of the Queen graph}},
author = {Martin Knor and Jelena Sedlar and Riste Škrekovski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.19024},
eprint = {2608.19024},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19024},
}
RIS
TY - UNPB
TI - On the odd independence number of the Queen graph
AU - Martin Knor
AU - Jelena Sedlar
AU - Riste Škrekovski
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2608.19024
UR - https://arxiv.org/abs/2608.19024
AB - 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.
ER -