首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Graphs with equal eternal vertex cover and eternal domination numbers
Authors:William F Klostermeyer  CM Mynhardt
Institution:aSchool of Computing, University of North Florida, Jacksonville, FL 32224-2669, United States;bDepartment of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, BC, Canada V8W 3R4
Abstract:Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.
Keywords:Eternal dominating set  Eternal vertex cover
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号