Ghebleh–Niepel conjecture on identifying codes in circulant graphs

At least 8 years old · documented by

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 n≥19n \geq 19 and n≡8(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 n≥11n\geq 11, including additional residue classes for sufficiently large nn.

References

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.