Online citations, reference lists, and bibliographies.

Edge Roman Domination On Graphs

G. J. Chang, Sheng-Hua Chen, C. Liu
Published 2016 · Mathematics, Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
An edge Roman dominating function of a graph G is a function $$f:E(G) \rightarrow \{0,1,2\}$$f:E(G)→{0,1,2} satisfying the condition that every edge e with $$f(e)=0$$f(e)=0 is adjacent to some edge $$e'$$e′ with $$f(e')=2$$f(e′)=2. The edge Roman domination number of G, denoted by $$\gamma '_R(G)$$γR′(G), is the minimum weight $$w(f) = \sum _{e\in E(G)} f(e)$$w(f)=∑e∈E(G)f(e) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree $$\Delta $$Δ on n vertices, then $$\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil $$γR′(G)≤⌈ΔΔ+1n⌉. While the counterexamples having the edge Roman domination numbers $$\frac{2\Delta -2}{2\Delta -1} n$$2Δ-22Δ-1n, we prove that $$\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}$$2Δ-22Δ-1n+22Δ-1 is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most $$\frac{6}{7}n$$67n, which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain $$K_{2,3}$$K2,3 as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.
This paper references



This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar