Existence of regular open and closed XOR-magic graphs of power-of-two order
Let be a positive integer, and let be a degree. An open XOR-magic graph and a closed XOR-magic graph are graphs admitting, respectively, an open or closed XOR-magic labeling. The graphs below are required to have order .
For each degree
there exists a -regular open XOR-magic graph of order . For each degree
there exists a -regular closed XOR-magic graph of order .
Existence conjecture. For every permitted degree in the two displayed sets, the corresponding regular open or closed XOR-magic graph exists. This would complete the existence picture apart from the degrees excluded by the previously stated nonexistence result and extend the constructions known for order and order to every order that is a power of two.
References
- Sylwia Cichacz, Hubert Grochowski and Rita Zuazua, “Open XOR-magic odd graphs and closed XOR-magic even graphs”, arXiv:2512.19278 (2025).
Progress summary
A 2025 paper proved existence in some degrees, while a November 2026 submission claims the remaining cases but has not been independently checked.
The 2025 paper of Cichacz, Grochowski, and Zuazua proves existence of at least one odd-regular open and one even-regular closed graph of order for every , but leaves the full degree-by-degree conjecture open. Its printed range also includes the already-forbidden closed degree .
Known results
- Batal proved nonexistence for closed degrees , equivalently open degrees .
- Cichacz, Grochowski, and Zuazua, December 23, 2025: proved at least one odd open and one even closed example for every , with explicit constructions for .
Community submission (unverified), November 7, 2026
A submitted proof argues that, after removing the forbidden endpoint , connected simple examples exist for every odd open degree from through and every even closed degree from through . This would settle the corrected conjecture, but the claim has not received independent mathematical assessment.
Current status (as of November 2026): the printed conjecture is false because closed degree is forbidden; the corrected all-degree statement is claimed solved by an unverified submission, while the independently documented literature leaves it open.
Sources
Solutions 1
The displayed closed degree 2^n - 4 is impossible for n >= 4. After removing that endpoint, the paper proves all intended odd-open and even-closed XOR-magic existence cases, with connected simple graphs.See full solution
Result and scope. Cichacz-Grochowski-Zuazua Conjecture 25 (arXiv:2512.19278) as printed is false at every n>=4 because closed degree 2^n-4 is excluded by Proposition 24 (Batal); that correction is zero-credit. The intended conjecture (MathDB: 'apart from the degrees excluded by the previously stated nonexistence result') is proved in full: for every n>=4 there are connected simple open zero-XOR graphs on 2^n vertices of every odd degree 5..2^n-5 and closed ones of every even degree 4..2^n-6, which with Proposition 24 is the complete existence picture for the odd-open and even-closed classes.
Complete proof: All corrected odd-open and even-closed XOR-magic degrees at powers of two · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.