The FKKR upper-bound conjecture for identifying codes

Let GG be a twin-free graph, let V(G)|V(G)| denote its number of vertices, and let ammaID(G)amma^{\text{\tiny{ID}}}(G) be its identifying code number. Write Δ(G)\Delta(G) for the maximum degree of GG. FKKR upper-bound conjecture. There exists a constant cc such that for every twin-free graph GG,

γID(G)V(G)V(G)Δ(G)+c.\gamma^{\text{\tiny{ID}}}(G) \leq |V(G)|- \frac{|V(G)|}{\Delta(G)}+c.

This conjecture proposes an upper bound improving the general bound γID(G)V(G)1\gamma^{\text{\tiny{ID}}}(G)\leq |V(G)|-1 in terms of the order and maximum degree of the graph. The supplied text gives no evidence that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov, “Identifying codes in line graphs”, arXiv:1107.0207 (2012).

Additional references

3 papers in this index state this conjecture (2010–2011). The statement above is taken from the most recent of them; the others are arXiv:1103.3756, arXiv:1010.5975.

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.