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

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.

Sources & referencesView supporting material

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.