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 K2 , 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