AIM-COMBINATORICS-0181 · Complete counterexample

Cyclic Counterexamples to the Exact-Distance Higher-Neighborhood Conjecture

Manuscript 18 October 2026 · Online 18 October 2026

math.COUnrefereed preprint

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
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}
}

More research papers

Show all 313 other papers

All 314 research papers →