## Abstract

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 K_{2 , 3} as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 1731-1747 |

Number of pages | 17 |

Journal | Graphs and Combinatorics |

Volume | 32 |

Issue number | 5 |

DOIs | |

State | Published - Sep 1 2016 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Keywords

- Edge Roman domination
- K-subdivision-free graph
- Planar graph
- Subcubic graph
- k-degenerate graph