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