ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


M. Blidia, A. Bouchou, M. Chellali


Extremal graphs for a bound on the Roman domination number


Discussiones Mathematicae Graph Theory

Received: 2017-12-11, Revised: 2018-04-24, Accepted: 2018-04-24,


A Roman dominating function on a graph $G=(V,E)$ is a function $f$:$V(G)\longrightarrow\{0,1,2\}$ such that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$. The weight of a Roman dominating function is the value $w(f)=\sum_{u\in V(G)}f(u)$. The minimum weight of a Roman dominating function on a graph $G$ is called the Roman domination number of $G$, denoted by $\gamma_{R}(G)$. In 2009, Chambers, Kinnersley, Prince and West proved that for any graph $G$ with $n$ vertices and maximum degree $\Delta$, $\gamma_{R}(G)\leq n+1-\Delta.$ In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether $\gamma_{R}(G)=n+1-\Delta$ is co-$\mathcal{NP}% $-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for $\gamma_{R}(G)+\gamma_{R}\big(\overline{G}\big),$ where $\overline{G}$ is the complement graph of $G.$


Roman domination, Roman domination number, Nordhaus-Gaddum inequalities