TY - JOUR
T1 - Edge Roman Domination on Graphs
AU - Chang, Gerard J.
AU - Chen, Sheng Hua
AU - Liu, Chun Hung
N1 - Funding Information:
G. J. Chang: Supported in part by the Ministry of Science and Technology under grant NSC101-2115-M-002-005-MY3.
Publisher Copyright:
© 2016, Springer Japan.
PY - 2016/9/1
Y1 - 2016/9/1
N2 - An edge Roman dominating function of a graph G is a function f: E(G) → { 0 , 1 , 2 } satisfying the condition that every edge e with f(e) = 0 is adjacent to some edge e′ with f(e′) = 2. The edge Roman domination number of G, denoted by γR′(G), is the minimum weight 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 Δ on n vertices, then γR′(G)≤⌈ΔΔ+1n⌉. While the counterexamples having the edge Roman domination numbers 2Δ-22Δ-1n, we prove that 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 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 K2 , 3 as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.
AB - An edge Roman dominating function of a graph G is a function f: E(G) → { 0 , 1 , 2 } satisfying the condition that every edge e with f(e) = 0 is adjacent to some edge e′ with f(e′) = 2. The edge Roman domination number of G, denoted by γR′(G), is the minimum weight 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 Δ on n vertices, then γR′(G)≤⌈ΔΔ+1n⌉. While the counterexamples having the edge Roman domination numbers 2Δ-22Δ-1n, we prove that 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 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 K2 , 3 as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.
KW - Edge Roman domination
KW - K-subdivision-free graph
KW - Planar graph
KW - Subcubic graph
KW - k-degenerate graph
UR - http://www.scopus.com/inward/record.url?scp=84962242937&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84962242937&partnerID=8YFLogxK
U2 - 10.1007/s00373-016-1695-x
DO - 10.1007/s00373-016-1695-x
M3 - Article
AN - SCOPUS:84962242937
SN - 0911-0119
VL - 32
SP - 1731
EP - 1747
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 5
ER -