تقرير
Total Roman {2}-Dominating functions in Graphs
العنوان: | Total Roman {2}-Dominating functions in Graphs |
---|---|
المؤلفون: | Ahangar, H. Abdollahzadeh, Chellali, M., Sheikholeslami, S. M., Valenzuela-Tripodoro, J. C. |
المصدر: | Discussiones Mathematicae Graph Theory 42 (2022) 937-958 |
سنة النشر: | 2024 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics |
الوصف: | A Roman $\{2\}$-dominating function (R2F) is a function $f:V\rightarrow \{0,1,2\}$ with the property that for every vertex $v\in V$ with $f(v)=0$ there is a neighbor $u$ of $v$ with $f(u)=2$, or there are two neighbors $x,y$ of $v$ with $f(x)=f(y)=1$. A total Roman $\{2\}$-dominating function (TR2DF) is an R2F $f$ such that the set of vertices with $f(v)>0$ induce a subgraph with no isolated vertices. The weight of a TR2DF is the sum of its function values over all vertices, and the minimum weight of a TR2DF of $G$ is the total Roman $\{2\}$-domination number $\gamma_{tR2}(G).$ In this paper, we initiate the study of total Roman $\{2\}$-dominating functions, where properties are established. Moreover, we present various bounds on the total Roman $\{2\}$-domination number. We also show that the decision problem associated with $\gamma_{tR2}(G)$ is NP-complete for bipartite and chordal graphs. {Moreover, we show that it is possible to compute this parameter in linear time for bounded clique-width graphs (including tres).} |
نوع الوثيقة: | Working Paper |
DOI: | 10.7151/dmgt.2316 |
URL الوصول: | http://arxiv.org/abs/2402.07968 |
رقم الأكسشن: | edsarx.2402.07968 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!