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


A. Cabrera Martínez, D. Kuziak, I.G. Yero


A constructive characterization of vertex cover Roman trees


Discussiones Mathematicae Graph Theory

Received: 2017-06-22, Revised: 2018-10-05, Accepted: 2018-10-05,


A Roman dominating function on a graph $G=(V(G),E(G))$ is a function $f : V(G)\rightarrow \{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. The Roman dominating function $f$ is an outer-independent Roman dominating function on $G$ if the set of vertices labeled with zero under $f$ is an independent set. The outer-independent Roman domination number $\gamma_{oiR}(G)$ is the minimum weight $w(f)=\sum_{v\in V(G)}f(v)$ of any outer-independent Roman dominating function $f$ of $G$. A vertex cover of a graph $G$ is a set of vertices that covers all the edges of $G$. The minimum cardinality of a vertex cover is denoted by $\alpha(G)$. A graph $G$ is a vertex cover Roman graph if $\gamma_{oiR}(G)=2\alpha(G)$. A constructive characterization of the vertex cover Roman trees is given in this article.


Roman domination, outer-independent Roman domination, vertex cover, vertex independence, trees