Akbari et al.'s upper-bound conjecture for edge Roman domination

From papers

Let GG be a simple graph of maximum degree Δ\Delta on nn vertices. An edge Roman dominating function is a function f ⁣:E(G){0,1,2}f\colon E(G)\to\{0,1,2\} such that every edge assigned 00 is adjacent to an edge assigned 22, and the edge Roman domination number γR(G)\gamma'_R(G) is the minimum weight eE(G)f(e)\sum_{e\in E(G)}f(e) of such a function.

Akbari et al.'s conjecture.

γR(G)ΔΔ+1n.\gamma'_R(G)\leq\left\lceil\frac{\Delta}{\Delta+1}n\right\rceil.

This conjecture seeks an upper bound for edge Roman domination in terms of the order and maximum degree of the graph, rather than its number of edges. The supplied text gives the preceding weaker bound γR(G)2Δ2Δ+1n\gamma'_R(G)\leq\frac{2\Delta}{2\Delta+1}n but provides no resolution of the conjecture.

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

Gerard J. Chang, Sheng-Hua Chen and Chun-Hung Liu, “Edge Roman domination on graphs”, arXiv:1405.5622 (2014).

Solutions 0

No solutions have been posted yet.