Iterated neighborhood graphs

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph ${\displaystyle (V,E_N)}$ where ${\displaystyle E_N}$ = {{a,b} | a ≠ b, {x,a} ∈ E and {x,b} ∈ E for some x ∈ V}. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph ${\displaystyle N^k\left(G\right):=N\left(N(...N\left(G\right))\right)}$ of G. In particular we investigate conditions for G and k such that ${\displaystyle N^k\left(G\right)}$ becomes a complete graph.