# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# 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

Authors:

M. Blidia, A. Bouchou, M. Chellali

Title:

Extremal graphs for a bound on the Roman domination number

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-12-11, Revised: 2018-04-24, Accepted: 2018-04-24, https://doi.org/10.7151/dmgt.2142

Abstract:

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.$

Keywords:

Roman domination, Roman domination number, Nordhaus-Gaddum inequalities