Discussiones Mathematicae Graph Theory 32(3) (2012)
403-417

doi: 10.7151/dmgt.1610

Martin Sonntag
Faculty of Mathematics and Computer Science | Hanns-Martin Teichert
Institute of Mathematics |

We present
some results concerning the *k-iterated neighborhood graph*
N^{k}(G) : = N(N( …N(G))) of G.
In particular we investigate conditions for G and k such that
N^{k}(G) becomes a complete graph.

**Keywords:** neighborhood graph, 2-step graph, neighborhood completeness number

**2010 Mathematics Subject Classification:** 05C76, 05C12.

[1] | B.D. Acharya and M.N. Vartak, Open neighborhood graphs, Indian Institute of Technology, Department of Mathematics, Research Report No. 7 (Bombay 1973). |

[2] | J.W. Boland, R.C. Brigham and R.D. Dutton, Embedding arbitrary graphs in neighborhood graphs, J. Combin. Inform. System Sci. 12 (1987) 101--112. |

[3] | R.C. Brigham and R.D. Dutton, On neighborhood graphs, J. Combin. Inform. System Sci. 12 (1987) 75--85. |

[4] | R. Diestel, Graph Theory, Second Edition, (Springer, 2000). |

[5] | G. Exoo and F. Harary, Step graphs, J. Combin. Inform. System Sci. 5 (1980) 52--53. |

[6] | H.J. Greenberg, J.R. Lundgren and J.S. Maybee, The inversion of , J. Combin. Inform. System Sci. 2-step graphs 8 (1983) 33--43. |

[7] | S.R. Kim, The competition number and its variants, in: Quo Vadis, Graph Theory?, J. Gimbel, J.W. Kennedy, L.V. Quintas (Eds.), Ann. Discrete Math. 55 (1993) 313--326. |

[8] | J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs and niche graphs, in: Applications of Combinatorics and Graph Theory to the
Biological and Social Sciences, F. Roberts (Ed.) (Springer, New York 1989) IMA 17
221?243. |

[9] | J.R. Lundgren, S.K. Merz, J.S. Maybee and C.W. Rasmussen, A characterization of graphs with interval two-step graphs, Linear Algebra Appl. 217 (1995) 203--223, doi: 10.1016/0024-3795(94)00173-B. |

[10] | J.R. Lundgren, S.K. Merz and C.W. Rasmussen, Chromatic numbers of competition graphs, Linear Algebra Appl. 217 (1995) 225--239, doi: 10.1016/0024-3795(94)00227-5. |

[11] | J.R. Lundgren and C. Rasmussen, Two-step graphs of trees, Discrete Math. 119 (1993) 123--139, doi: 10.1016/0012-365X(93)90122-A. |

[12] | J.R. Lundgren, C.W. Rasmussen and J.S. Maybee, Interval competition graphs of symmetric digraphs, Discrete Math. 119 (1993) 113--122, doi: 10.1016/0012-365X(93)90121-9. |

[13] | M.M. Miller, R.C. Brigham and R.D. Dutton, An equation involving the neighborhood , Ars Combin. (two step) and line graphs 52 (1999) 33--50. |

[14] | M. Pfützenreuter, Konkurrenzgraphen von ungerichteten Graphen (Bachelor thesis, University of Lübeck, 2006). |

[15] | F.S. Roberts, Competition graphs and phylogeny graphs,
in: Graph Theory and Combinatorial Biology, Proceedings of International Colloquium Balatonlelle (1996),
Bolyai Society of Mathematical Studies, L. Lovász (Ed.) (Budapest, 1999) 7, 333?362. |

[16] | I. Schiermeyer, M. Sonntag and H.-M. Teichert, Structural properties and hamiltonicity of neighborhood graphs, Graphs Combin. 26 (2010) 433--456, doi: 10.1007/s00373-010-0909-x. |

[17] | P. Schweitzer (Max-Planck-Institute for Computer Science, Saarbr{ü}cken, Germany), unpublished script (2010). |

Received 12 January 2011

Revised 14 July 2011

Accepted 18 July 2011