پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,682 |
| تعداد مقالات | 13,758 |
| تعداد مشاهده مقاله | 32,158,499 |
| تعداد دریافت فایل اصل مقاله | 12,733,695 |
A dynamic domination problem in trees | ||
| Transactions on Combinatorics | ||
| مقاله 3، دوره 4، شماره 4، اسفند 2015، صفحه 15-31 اصل مقاله (270.98 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2015.7590 | ||
| نویسندگان | ||
| William Klostermeyer* 1؛ Christina Mynhardt2 | ||
| 1School of Computing University of North Florida | ||
| 2Department of Mathematics and Statistics University of Victoria | ||
| چکیده | ||
| We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack and the resulting guard movements, the vertices containing guards form a dominating set of the graph. The minimum number of guards that can successfully defend the graph against such an arbitrary sequence of attacks is the m-eviction number. This parameter lies between the domination and independence numbers of the graph. We characterize the classes of trees for which the m-eviction number equals the domination number and the independence number, respectively. | ||
| کلیدواژهها | ||
| graph protection؛ eternal domination؛ Domination Number؛ Independence number | ||
| مراجع | ||
|
M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray and J. Yellen (2007) Maximum demand graphs for eternal security J. Combin. Math. Combin. Comput. 61, 111-128
A. P. Burger, E. J. Cockayne, W. R. Grundlingh, C. M. Mynhardt, J. H. van Vuuren and W. Winterbach (2004) Infinite order domination in graphs J. Combin. Math. Combin. Comput. 50, 179-194
E. J. Cockayne, O. Favaron, C. M. Mynhardt and J. Puech (2000) A characterisation of $(\gamma,i)$-trees J. Graph Theory 34, 277-292
M. Dorfling, W. Goddard, M A. Henning and C. M. Mynhardt (2006) Construction of trees and graphs with equal domination parameters Discrete Math. 306, 2647-2654
W. Goddard, S. M. Hedetniemi and S. T. Hedetniemi (2005) Eternal security in graphs J. Combin. Math. Combin. Comput. 52, 169-180
J. Goldwasser and W. F. Klostermeyer (2008) Tight bounds for eternal dominating sets in graphs Discrete Math. 308, 2589-2593
J. L. Goldwasser, W. F. Klostermeyer and C. M. Mynhardt (2013) Eternal protection in grid graphs Util. Math. 91, 47-64
W. F. Klostermeyer, M. Lawrence and G. MacGillivray An eternal domination problem related to file migration to appear in J. Combin. Math. Combin. Comput.
W. F. Klostermeyer and G. MacGillivray (2007) Eternal security in graphs of fixed independence number J. Combin. Math. Combin. Comput. 63, 97-101
W. F. Klostermeyer and G. MacGillivray (2009) Eternal dominating sets in
graphs J. Combin. Math. Combin. Comput. 68, 97-111
W. F. Klostermeyer and C. M. Mynhardt (2009) Edge protection in graphs Australas. J. Combin. 45, 235-250
W. F. Klostermeyer and C. M. Mynhardt (2011) Graphs with equal eternal vertex cover and eternal domination numbers Discrete Math. 311, 1371-1379
W. F. Klostermeyer and C. M. Mynhardt (2012) Vertex covers and eternal dominating sets Discrete Appl. Math. 160, 1183-1190
W. F. Klostermeyer and C. M. Mynhardt (2012) Eternal total domination in graphs Ars Combin 107, 473-492
C. M. Mynhardt (1999) Vertices contained in every minimum dominating set of a tree J. Graph Theory 31, 163-177
| ||
|
آمار تعداد مشاهده مقاله: 4,279 تعداد دریافت فایل اصل مقاله: 3,623 |
||