The DET:OLD density conjecture for C4C_4-free cubic graphs

About 3 years old · traced to

Let GG be a C4C_4-free cubic graph, and let DET:OLD%(G)\%(G) denote the minimum density of an error-detecting open-locating-dominating set in GG. DET:OLD density conjecture.

DET:OLD%(G)≤2122.\textrm{DET:OLD}\%(G) \leq \frac{21}{22}.

The bound would improve the general upper bound DET:OLD%(G)≤3031\%(G) \leq \frac{30}{31} for cubic graphs that permit DET:OLD, and is motivated by the extremal cubic graphs found on 1616 through 2424 vertices. Whether 2122\frac{21}{22} is the tight upper bound for all relevant cubic graphs remains open.

References

Primary source

Devin Jean and Suk Seo, “On Error-detecting Open-locating-dominating sets”, arXiv:2306.12583 (2023).

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.