Ghebleh–Niepel conjecture on identifying codes in circulant graphs
Ghebleh–Niepel conjecture on identifying codes in circulant graphs
Let be the circulant graph on vertex set in which vertices at cyclic distances or are adjacent. An identifying code is a dominating vertex set whose closed neighborhoods intersected with the code are distinct for all vertices; let denote the minimum size of such a code. Ghebleh–Niepel's conjecture. If is an integer such that and , then
The paper proves this conjecture and, more broadly, determines the exact identifying-code number for all , including additional residue classes for sufficiently large .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.