The asymptotic weighted domination bound for connected subcubic planar graphs

From papers

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.

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

Eun-Kyung Cho, Eric Culver, Stephen G. Hartke and Vesna Iršič, “Domination of subcubic planar graphs with large girth”, arXiv:2312.03384 (2023).

Solutions 0

No solutions have been posted yet.