Cyclic Counterexamples to the Exact-Distance Higher-Neighborhood Conjecture
Manuscript 18 October 2026 · Online 18 October 2026
Abstract
For every integer k>=3 and n>k(k+1), the oriented cyclic Cayley graph with increments 1,k,k+1 has directed girth greater than k, yet every vertex has 2k-1 vertices at shortest directed distance k-1 and only k+1 at distance k. This gives complete counterexamples to the exact-distance higher-neighborhood assertion printed as Conjecture 6.13 in Sullivan's 2006 survey, corresponding to AIM-COMBINATORICS-0181. The graphs are strongly connected, vertex-transitive, and three-in/three-out regular, with arbitrarily large directed girth at each fixed k. Independent blow-ups yield unbounded degrees and deficits. An elementary integer sumset identity proves the general construction; a thirteen-vertex example and 3,546 exact checks per execution mode supplement the proof. The k=2 second-neighborhood problem and a different recursive external-neighborhood formulation are not resolved. AI-assisted, self-audited and unrefereed; no formal verification, independent peer review, global minimality, or absolute priority is claimed.
Record
- Affiliation
- Mercury Software GmbH
- Contact
- [email protected] · GitHub
- Result
- Complete counterexample
- Categories
- math.CO
- Manuscript
- 18 October 2026
- Online release
- 18 October 2026
- Version
- 1.0
- License
- Creative Commons Attribution 4.0 International
Files and verification
The PDF is the canonical reading copy. The source archive contains the LaTeX manuscript, bibliography, reproducibility material, and audit documents without build artefacts.
Citation
Alper Ferudun, “Cyclic Counterexamples to the Exact-Distance Higher-Neighborhood Conjecture,” EulerSolve Research Papers, AIM-COMBINATORICS-0181, 2026. https://doi.org/10.5281/zenodo.23445795.
BibTeX
@misc{ferudun2026cyclicneighborhoods,
author = {Ferudun, Alper},
title = {Cyclic Counterexamples to the Exact-Distance Higher-Neighborhood Conjecture},
year = {2026},
howpublished = {EulerSolve Research Papers},
url = {https://eulersolve.org/papers/aim-combinatorics-0181/},
doi = {10.5281/zenodo.23445795},
note = {AIM-COMBINATORICS-0181; unrefereed preprint}
}