|
|
|
|
a dynamic domination problem in trees
|
|
|
|
|
|
|
|
نویسنده
|
KLOSTERMEYER WILLIAM F. ,MYNHARDT CHRISTINA
|
|
منبع
|
transactions on combinatorics - 2015 - دوره : 4 - شماره : 4 - صفحه:15 -31
|
|
چکیده
|
We consider a dynamic domination problem for graphs in which an infinitesequence of attacks occur at vertices with guards and the guard at theattacked vertex is required to vacate the vertex by moving to a neighboringvertex with no guard. other guards are allowed to move at the same time, andbefore and after each attack and the resulting guard movements, the verticescontaining guards form a dominating set of the graph. the minimum number ofguards that can successfully defend the graph against such an arbitrarysequence of attacks is the m-eviction number. this parameter lies between thedomination and independence numbers of the graph.we characterize the classes of trees for which the m-eviction number equalsthe domination number and the independence number, respectively.
|
|
کلیدواژه
|
graph protection ,eternal domination ,domination number ,independence number
|
|
آدرس
|
University of North Florida, School of Computing, USA, University of Victoria, Department of Mathematics and Statistics, Canada
|
|
پست الکترونیکی
|
kieka@uvic.ca
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|