The asymptotic weighted domination bound for connected subcubic planar graphs

About 3 years old · traced to

Let GG be a connected subcubic planar graph, and for i∈{0,1,2,3}i\in\{0,1,2,3\} let ni(G)n_i(G) denote the number of vertices of degree ii in GG. Let γ(G)\gamma(G) denote the domination number of GG. The conjectured optimal bound. There exists a constant NN such that every such graph with at least NN vertices satisfies

γ(G)≤n0(G)+1320n1(G)+12n2(G)+720n3(G).\gamma(G) \leq n_0(G) + \frac{13}{20} n_1(G) + \frac{1}{2} n_2(G) + \frac{7}{20} n_3(G).

The conjecture is motivated by a constructed family showing that the coefficient 12\frac{1}{2} on n2(G)n_2(G) would make the paper's upper bound tight. The source gives no resolution.

References

Primary source

Eun-Kyung Cho, Eric Culver, Stephen G. Hartke and Vesna Iršič, “Domination of subcubic planar graphs with large girth”, arXiv:2312.03384 (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.