## Abstract

A Roman dominating function of a graph G is a function f: V (G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u) = 2. The weight of fis w(f) = ΣvεV (G) f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince, andWest [SIAM J. Discrete Math., 23 (2009), pp. 1575-1586] conjectured that γR(G) ≤ [2n/3] for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that γR(G) = max{[2n/3], 23n/34} for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which γR(G) = 23n/34 when 23n/34 > [2n/3].

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

Pages (from-to) | 193-205 |

Number of pages | 13 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 26 |

Issue number | 1 |

DOIs | |

State | Published - 2012 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- 2-connected graph
- Domination
- Roman domination