Geodesic
Vertex-Edge Roman Domination
Kragujevac Journal of Mathematics, Tome 45 (2021) no. 5, p. 685

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

A vertex-edge Roman dominating function (or just ve-RDF) of a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2\}$ such that for each edge $e=uv$ either $\max \{f(u),f(v)\}\neq 0$ or there exists a vertex $w$ such that either $wu\in E$ or $wv\in E$ and $f(w)=2$. The weight of a ve-RDF is the sum of its function values over all vertices. The vertex-edge Roman domination number of a graph $G$, denoted by $\gamma _{veR}(G)$, is the minimum weight of a ve-RDF $G$. In this paper, we initiate a study of vertex-edge Roman dominaton. We first show that determining the number $\gamma _{veR}(G)$ is NP-complete even for bipartite graphs. Then we show that if $T$ is a tree different from a star with order $n$, $l$ leaves and $s $ support vertices, then $\gamma _{veR}(T)\geq (n-l-s+3)/2$, and we characterize the trees attaining this lower bound. Finally, we provide a characterization of all trees with $\gamma _{veR}(T)=2\gamma ^{\prime }(T)$, where $\gamma ^{\prime }(T)$ is the edge domination number of $T$.
Classification : 05C69
Keywords: vertex-edge roman dominating set, edge dominating set, trees 
@article{KJM_2021_45_5_a1,
     author = {H. Naresh Kumar and Y. B. Venkatakrishnan},
     title = {Vertex-Edge {Roman} {Domination}},
     journal = {Kragujevac Journal of Mathematics},
     pages = {685 },
     publisher = {mathdoc},
     volume = {45},
     number = {5},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KJM_2021_45_5_a1/}
}
TY  - JOUR
AU  - H. Naresh Kumar
AU  - Y. B. Venkatakrishnan
TI  - Vertex-Edge Roman Domination
JO  - Kragujevac Journal of Mathematics
PY  - 2021
SP  - 685 
VL  - 45
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KJM_2021_45_5_a1/
LA  - en
ID  - KJM_2021_45_5_a1
ER  - 
%0 Journal Article
%A H. Naresh Kumar
%A Y. B. Venkatakrishnan
%T Vertex-Edge Roman Domination
%J Kragujevac Journal of Mathematics
%D 2021
%P 685 
%V 45
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KJM_2021_45_5_a1/
%G en
%F KJM_2021_45_5_a1
H. Naresh Kumar; Y. B. Venkatakrishnan. Vertex-Edge Roman Domination. Kragujevac Journal of Mathematics, Tome 45 (2021) no. 5, p. 685 . http://geodesic.mathdoc.fr/item/KJM_2021_45_5_a1/