The FKKR upper-bound conjecture for identifying codes

At least 15 years old · documented by

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.

References

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.