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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.