تقرير
Maximal double Roman domination in graphs
العنوان: | Maximal double Roman domination in graphs |
---|---|
المؤلفون: | Ahangar, H. Abdollahzadeh, Chellali, M., Sheikholeslami, S. M., Valenzuela-Tripodoro, J. C. |
المصدر: | Applied Mathematics and Computation 414 (2022) 126662 |
سنة النشر: | 2024 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics |
الوصف: | A maximal double Roman dominating function (MDRDF) on a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2,3\}$ such that \textrm{(i) }every vertex $v$ with $f(v)=0$ is adjacent to least two vertices { assigned $2$ or to at least one vertex assigned $3,$} \textrm{(ii) }every vertex $v$ with $f(v)=1$ is adjacent to at least one { vertex assigned $2$ or $3$} and \textrm{(iii) }the set $\{w\in V|~f(w)=0\}$ is not a dominating set of $G $. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number $\gamma _{dR}^{m}(G) $ is the minimum weight of an MDRDF on $G$. {In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining }$\gamma _{dR}^{m}(G)$ {is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating }$\gamma _{dR}^{m}(G)$ to some domination parameters. {For the class of trees, we show that for every tree }$T$ {of order }$n\geq 4,$ $\gamma _{dR}^{m}(T)\leq \frac{5}{4}n$ {and we characterize all trees attaining the bound. Finally, the exact values of }$\gamma _{dR}^{m}(G) $ {are given for paths and cycles. |
نوع الوثيقة: | Working Paper |
DOI: | 10.1016/j.amc.2021.126662 |
URL الوصول: | http://arxiv.org/abs/2402.07013 |
رقم الأكسشن: | edsarx.2402.07013 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!