Ghebleh–Niepel conjecture on identifying codes in circulant graphs

Let Cn(1,3)C_n(1,3) be the circulant graph on vertex set Zn\mathbb{Z}_n in which vertices at cyclic distances 11 or 33 are adjacent. An identifying code is a dominating vertex set whose closed neighborhoods intersected with the code are distinct for all vertices; let γID(Cn(1,3))\gamma^{ID}(C_n(1,3)) denote the minimum size of such a code. Ghebleh–Niepel's conjecture. If nn is an integer such that n19n \geq 19 and n8(mod11)n \equiv 8 \pmod{11}, then

γID(Cn(1,3))=4n/11+1.\gamma^{ID}(C_n(1,3))=\lceil 4n/11\rceil+1.

The paper proves this conjecture and, more broadly, determines the exact identifying-code number for all n11n\geq 11, including additional residue classes for sufficiently large nn.

Sources & referencesView supporting material

Primary source

Ville Junnila, Tero Laihonen and Gabrielle Paris, “Solving Two Conjectures regarding Codes for Location in Circulant Graphs”, arXiv:1710.00605 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.