آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,562 |
| تعداد دریافت فایل اصل مقاله | 1,060,275 |
Mixed Roman domination and 2-independence in trees | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 6، دوره 3، شماره 1، شهریور 2018، صفحه 79-91 اصل مقاله (426.14 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2018.25964.1062 | ||
| نویسنده | ||
| Nasrin Dehgardi* | ||
| Sirjan University of Technology, Sirjan 78137, Iran | ||
| چکیده | ||
| Let $G=(V, E)$ be a simple graph with vertex set $V$ and edge set $E$. A em mixed Roman dominating function (MRDF) of $G$ is a function $f:V\cup E\rightarrow \{0,1,2\}$ satisfying the condition that every element $xin V\cup E$ for which $f(x)=0$ is adjacent or incident to at least one element $y\in V\cup E$ for which $f(y)=2$. The weight of an MRDF $f$ is $\sum_{x\in V\cup E} f(x)$. The mixed Roman domination number $\gamma^*_R(G)$ of $G$ is the minimum weight among all mixed Roman dominating functions of $G$. A subset $S$ of $V$ is a 2-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The minimum cardinality of a 2-independent set of $G$ is the 2-independence number $\beta_2(G)$. These two parameters are incomparable in general, however, we show that if $T$ is a tree, then $\frac{4}{3}\beta_2(T)\ge \gamma^*_R(T)$ and we characterize all trees attaining the equality. | ||
| کلیدواژهها | ||
| Mixed Roman dominating function؛ Mixed Roman domination number؛ 2-independent set؛ 2-independence number | ||
| مراجع | ||
|
[1] H. Abdollahzadeh Ahangar, T.W. Haynes, and J.C. Valenzuela-Tripodoro, Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc. 40 (2017), no. 4, 1443–1454.
[2] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-domination and kindependence in graphs: A survey, Graphs Combin. 28 (2012), no. 1, 1–55.
[3] 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.
[4] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451.
[5] J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, Inc., 1985, pp. 301–311.
[6] C.-H. Liu and G.J. Chang, Roman domination on 2-connected graphs, SIAM J. Discrete Math. 26 (2012), no. 1, 193–205.
[7] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012), no. 7, 1386–1391.
[8] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
[9] P. Pavlić and J. Žerovnik, Roman domination number of the cartesian products of paths and cycles, Electron. J. Combin. 19 (2012), no. 3, 19.
[10] 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.
[11] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[12] D.B. West, Introduction to graph theory, vol. 2, Prentice hall Upper Saddle River, 2001.
[13] I.G. Yero and J.A. Rodrigoez Velázquez, Roman domination in cartesian product graphs and strong product graphs, Appl. Anal. Discrete Math. 7 (2013), no. 2, 262–274. | ||
|
آمار تعداد مشاهده مقاله: 1,184 تعداد دریافت فایل اصل مقاله: 637 |
||