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


Dynamic monopolies and feedback vertex sets in hexagonal grids
Authors:Sarah Spence Adams  S. Luke Zinnen
Affiliation:
  • a Franklin W. Olin College of Engineering, Olin Way, Needham, MA 02492, USA
  • b Babson College, Babson Park, MA 02457, USA
  • Abstract:In a majority conversion process, the vertices of a graph can be in one of the two states, colored or uncolored, and these states are dynamically updated so that a vertex becomes colored at a certain time period if at least half of its neighbors were in the colored state in the previous time period. A dynamic monopoly is a set of vertices in a graph that when initially colored will eventually cause all vertices in the graph to become colored. This paper establishes a connection between dynamic monopolies and the well-known feedback vertex sets which are sets of vertices whose removal results in an acyclic graph. More specifically, we show that dynamic monopolies and feedback vertex sets are equivalent in graphs wherein all vertices have degree 2 or 3. We use this equivalence to provide exact values for the minimum size of dynamic monopolies of planar hexagonal grids, as well as upper and lower bounds on the minimum size of dynamic monopolies of cylindrical and toroidal hexagonal grids. For these last two topologies, the respective upper and lower bounds differ by at most one.
    Keywords:Dynamic monopoly   Dynamo   Feedback vertex set   Hexagonal grid   Majority conversion process   Target set selection
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

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