تعداد نشریات | 5 |
تعداد شمارهها | 111 |
تعداد مقالات | 1,247 |
تعداد مشاهده مقاله | 1,199,566 |
تعداد دریافت فایل اصل مقاله | 1,060,282 |
Double Roman domination and domatic numbers of graphs | ||
Communications in Combinatorics and Optimization | ||
مقاله 5، دوره 3، شماره 1، شهریور 2018، صفحه 71-77 اصل مقاله (409.04 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2018.26125.1078 | ||
نویسنده | ||
Lutz Volkmann* | ||
RWTH Aachen University | ||
چکیده | ||
A double Roman dominating function on a graph $G$ with vertex set $V(G)$ is defined in cite{bhh} as a function $f:V(G)\to \{0,1,2,3\}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must have at least one neighbor $u$ with $f(u)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $\sum_{v\in V(G)}f(v)$, and the minimum weight of a double Roman dominating function on $G$ is the double Roman domination number $\gamma_{dR}(G)$ of $G$. A set $\{f_1,f_2, \dots,f_d\}$ of distinct double Roman dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 3$ for each $v\in V(G)$ is called a double Roman dominating family (of functions) on $G$. The maximum number of functions in a double Roman dominating family on $G$ is the double Roman domatic number of $G$. In this note we continue the study the double Roman domination and domatic numbers. In particular, we present a sharp lower bound on $\gamma_{dR}(G)$, and we determine the double Roman domination and domatic numbers of some classes of graphs. | ||
کلیدواژهها | ||
domination؛ Double Roman domination number؛ Double Roman domatic number | ||
مراجع | ||
[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Atapour, M. Chellali, and S.M. Sheikholeslami, Double Roman trees, Ars Combin. (to apeear).
[2] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A Sci. (to apeear).
[3] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[5] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575–1586.
[6] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[7] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[8] N. Jafari Rad and H. Rahbani, Some progress on double Roman domination in graphs, Discuss. Math. Graph Theory (to apeear).
[9] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[10] S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010), no. 10, 1295–1300.
[11] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[12] L. Volkmann, The double Roman domatic number of a graph, J. Combin. Math. Combin. Comput. 104 (2018), 205–215. | ||
آمار تعداد مشاهده مقاله: 1,537 تعداد دریافت فایل اصل مقاله: 1,404 |