DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

Article in press


Authors:

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

Title:

A constructive characterization of vertex cover Roman trees

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-06-22, Revised: 2018-10-05, Accepted: 2018-10-05, https://doi.org/10.7151/dmgt.2179

Abstract:

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.

Keywords:

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

PDF
Close