Geodesic
Vertex-Edge Roman Domination
Kragujevac Journal of Mathematics, Tome 45 (2021) no. 5, p. 685 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 },
     year = {2021},
     volume = {45},
     number = {5},
     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
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
%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/