Iterated open neighborhood graphs and generalizations

作者：Schweitzer Pascal^*

来源：Discrete Applied Mathematics, 2013, 161(10-11): 1598-1609.

DOI：10.1016/j.dam.2012.12.023

• Neighborhood graphs
• Iterated replacement
• Conway's Game of Life

The open neighborhood graph of an undirected graph G is the graph that is defined on the same vertex set as Gin which two vertices are adjacent, if they have a common neighbor in G. We analyze the graphs obtained by repeatedly applying the open neighborhood graph construction. We show that stab(G), the number of iterations required for the process to stabilize, is at most 2 larger than the logarithm of the diameter of G rounded up. We also show that for graphs that eventually become a clique, the number of iterations is at least the logarithm of the diameter of G rounded up. That is inverted right perpendicularlog(2)(diam(G))inverted left perpendicular <= stab(G) <= inverted right perpendicularlog(2)(diam(G))inverted left perpendicular + 2. These bounds are tight.
We also consider the process of repeatedly forming H-neighborhood graphs. For a graph H with two distinguished vertices, the H-neighborhood graph of G is the graph defined on the same vertex set as G in which two vertices are adjacent if they form the distinguished vertices in a (not necessarily induced) subgraph of G isomorphic to H. If the distinguished vertices of H are adjacent, then the number of iterations for the process to stabilize is at most linear in the number of edges of G. If the distinguished vertices of H are not required to be adjacent, we show that the number of iterations may be exponential. To prove this we show that there is a graph H for which the process of forming H-neighborhood graphs can simulate Conway's Game of Life.

• 出版日期2013-7