Iterated open neighborhood graphs and generalizations

The open neighborhood graph of an undirected graph GG is the graph that is defined on the same vertex set as GG in which two vertices are adjacent, if they have a common neighbor in GG. We analyze the graphs obtained by repeatedly applying the open neighborhood graph construction. We show that stab(G)stab(G), the number of iterations required for the process to stabilize, is at most 2 larger than the logarithm of the diameter of GG 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 GG rounded up. That is ⌈log2(diam(G))⌉≤stab(G)≤⌈log2(diam(G))⌉+2⌈log2(diam(G))⌉≤stab(G)≤⌈log2(diam(G))⌉+2. These bounds are tight.We also consider the process of repeatedly forming HH-neighborhood graphs. For a graph HH with two distinguished vertices, the HH-neighborhood graph of GG is the graph defined on the same vertex set as GG in which two vertices are adjacent if they form the distinguished vertices in a (not necessarily induced) subgraph of GG isomorphic to HH. If the distinguished vertices of HH are adjacent, then the number of iterations for the process to stabilize is at most linear in the number of edges of GG. If the distinguished vertices of HH 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 HH for which the process of forming HH-neighborhood graphs can simulate Conway’s Game of Life.