The lower-bound conjecture for DET:IC density in cubic graphs

At least 3 years old · documented by

Let GG be a cubic graph, and let DET:IC%(G)(G) denote the minimum density of a deterministic error-detecting identifying code in GG. Lower-bound conjecture.

DET:IC%(G)≥34.\textrm{DET:IC\%}(G) \ge \frac{3}{4}.

The paper identifies 34\frac{3}{4} as the lowest value found for cubic graphs and exhibits infinite families attaining this density. Whether every cubic graph satisfies the bound remains conjectural in the provided text.

References

Primary source

Devin Jean and Suk Seo, “Optimal Error-detection system for Identifying Codes”, arXiv:2208.06052 (2022).

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.