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

About 12 years old · traced to

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 ∑e∈E(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.

References

Primary source

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

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.