Bounding the rainbow domination number of a tree in terms of its annihilation number

Dehgardi, Nasrin; Sheikholeslami, Mahmoud; Khodkar, Abdollah

doi:10.22108/toc.2013.3051

تعداد نشریات	43
تعداد شماره‌ها	1,686
تعداد مقالات	13,791
تعداد مشاهده مقاله	32,396,032
تعداد دریافت فایل اصل مقاله	12,795,239

	Bounding the rainbow domination number of a tree in terms of its annihilation number
Transactions on Combinatorics
مقاله 3، دوره 2، شماره 3، آذر 2013، صفحه 21-32 اصل مقاله (339.91 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2013.3051
نویسندگان
Nasrin Dehgardi¹؛ Mahmoud Sheikholeslami¹؛ Abdollah Khodkar^* ²
¹Azarbaijan Shahid Madani University
²University Of West Georgia
چکیده
A $2$-rainbow dominating function (2RDF) of a graph $G$ is a‎ ‎function $f$ from the vertex set $V(G)$ to the set of all subsets‎ ‎of the set $\{1,2\}$ such that for any vertex $v\in V(G)$ with‎ ‎$f(v)=\emptyset$ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$‎ ‎is fulfilled‎, ‎where $N(v)$ is the open neighborhood of $v$‎. ‎The ‎weight of a 2RDF $f$ is the value $\omega(f)=\sum_{v\in V}\|f‎ ‎(v)\|$‎. ‎The $2$-rainbow domination number of a graph $G$‎, ‎denoted by $\gamma_{r2}(G)$‎, ‎is the minimum weight of a 2RDF of G‎. ‎The annihilation number $a(G)$ is the largest integer $k$ such‎ ‎that the sum of the first $k$ terms of the non-decreasing degree‎ ‎sequence of $G$ is at most the number of edges in $G$‎. ‎In this‎ ‎paper‎, ‎we prove that for any tree $T$ with at least two vertices‎, ‎$\gamma_{r2}(T)\le a(T)+1$‎.
کلیدواژه‌ها
annihilation number؛ 2-rainbow dominating function؛ 2-rainbow domination number

مراجع
N. Dehgardai, S. Norouzian and S. M. Sheikholeslami (2013) Bounding the domination number of a tree in terms of its annihilation number Trans. Comb. 2 (1), 9-16 B. Brechecksar, M. A. Henning and D. F. Rall (2008) Rainbow domination in graphs Taiwanese J. Math. 12, 213-225 B. Brechecksar and T. K. Sumenjak (2007) On the 2-rainbow domination in graphs Discrete Appl. Math. 155, 2394-2400 G. J. Chang, J. Wu and X. Zhu (2010) Rainbow domination on trees Discrete Appl. Math. 158, 8-12 T. Chunling, L. Xiaohui, Y. Yuansheng and L. Meiqin (2009) 2-rainbow domination of generalized Petersen graphs P(n,2) Discrete Appl. Math. 157, 1932-1937 W. J. Desormeaux, T. W. Haynes and M. A. Henning (2013) Relating the annihilation number and the total domination number of a tree Discrete Appl. Math. 161, 349-354 C. E. Larson and R. Pepper (2011) Graphs with equal independence and annihilation numbers The Electron. J. Combin. 18, 0 D. Meierling, S. M. Sheikholeslami and L. Volkmann (2011) Nordhaus-Gaddum bounds on the $k$-rainbow domatic number of a graph Appl. Math. Lett. 24, 1758-1761 R. Pepper (2004) Binding Independence Ph.D. Dissertation, University of Houston R. Pepper (2009) On the annihilation number of a graph Recent Advances In Electrical Engineering: Proceedings of the 15th American Conference on Applied Mathematics , 217-220 S. M. Sheikholeslami and L. Volkmann (2012) The k-rainbow domatic number of a graph Discuss. Math. Graph Theory 32, 129-140 Y. Wu and N. Jafari Rad (2013) Bounds on the 2-rainbow domination number of graphs Graphs Combin. 29 (4), 1125-1133 G. Xu (2009) 2-rainbow domination of generalized Petersen graphs P(n,3) Discrete Appl. Math. 157, 2570-2573
آمار تعداد مشاهده مقاله: 4,501 تعداد دریافت فایل اصل مقاله: 3,152

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Bounding the rainbow domination number of a tree in terms of its annihilation number