Roman Domination on 2-Connected Graphs
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 26 (1), 193-205
- https://doi.org/10.1137/080733085
Abstract
A Roman dominating function of a graph $G$ is a function $f$$: V(G) \to \{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 $f$ is $w(f) = \sum_{v \in V(G)} f(v)$. The Roman domination number $\gamma_R(G)$ of $G$ is the minimum weight of a Roman dominating function of $G$. Chambers, Kinnersley, Prince, and West [SIAM J. Discrete Math., 23 (2009), pp. 1575-1586] conjectured that $\gamma_R(G) \le \lceil 2n/3 \rceil$ for any $2$-connected graph $G$ of $n$ vertices. This paper gives counterexamples to the conjecture and proves that $\gamma_R(G) \le \max\{\lceil 2n/3 \rceil, 23n/34\}$ for any $2$-connected graph $G$ of $n$ vertices. We also characterize $2$-connected graphs $G$ for which $\gamma_R(G) = 23n/34$ when $23n/34 \lceil 2n/3 \rceil$.
Keywords
This publication has 10 references indexed in Scilit:
- Extremal Problems for Roman DominationSIAM Journal on Discrete Mathematics, 2009
- ROMAN DOMINATION: a parameterized perspective†International Journal of Computer Mathematics, 2008
- A note on Roman domination in graphsDiscrete Mathematics, 2006
- Roman domination in graphsDiscrete Mathematics, 2004
- Defending the Roman Empire from multiple attacksDiscrete Mathematics, 2003
- Defending the Roman Empire—A new strategyDiscrete Mathematics, 2003
- A characterization of Roman treesDiscussiones Mathematicae Graph Theory, 2002
- Defendens Imperium Romanum: A Classical Problem in Military StrategyThe American Mathematical Monthly, 2000
- Defend the Roman Empire!Scientific American, 1999
- On minimal blocksTransactions of the American Mathematical Society, 1968