# Iterated neighborhood graphs

Martin Sonntag; Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 3, page 403-417
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMartin Sonntag, and Hanns-Martin Teichert. "Iterated neighborhood graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 403-417. <http://eudml.org/doc/270787>.

@article{MartinSonntag2012,

abstract = {The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $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 $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.},

author = {Martin Sonntag, Hanns-Martin Teichert},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {neighborhood graph; 2-step graph; neighborhood completeness number},

language = {eng},

number = {3},

pages = {403-417},

title = {Iterated neighborhood graphs},

url = {http://eudml.org/doc/270787},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Martin Sonntag

AU - Hanns-Martin Teichert

TI - Iterated neighborhood graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 3

SP - 403

EP - 417

AB - The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $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 $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.

LA - eng

KW - neighborhood graph; 2-step graph; neighborhood completeness number

UR - http://eudml.org/doc/270787

ER -

## References

top- [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. Zbl0696.05021
- [3] R.C. Brigham and R.D. Dutton, On neighborhood graphs, J. Combin. Inform. System Sci. 12 (1987) 75-85. Zbl0668.05056
- [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 2-step graphs, J. Combin. Inform. System Sci. 8 (1983) 33-43. Zbl0631.05044
- [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. Zbl0821.05045
- [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. Zbl0821.05024
- [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. Zbl0790.05023
- [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. Zbl0790.05036
- [13] M.M. Miller, R.C. Brigham and R.D. Dutton, An equation involving the neighborhood (two step) and line graphs, Ars Combin. 52 (1999) 33-50. Zbl0977.05111
- [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. Zbl0924.05032
- [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. Zbl1258.05064
- [17] P. Schweitzer (Max-Planck-Institute for Computer Science, Saarbrücken, Germany), unpublished script (2010).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.