Iterated neighborhood graphs

Martin Sonntag; Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory (2012)

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

Abstract

top
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.

How to cite

top

Martin 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. [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. [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. [3] R.C. Brigham and R.D. Dutton, On neighborhood graphs, J. Combin. Inform. System Sci. 12 (1987) 75-85. Zbl0668.05056
  4. [4] R. Diestel, Graph Theory, Second Edition, (Springer, 2000). 
  5. [5] G. Exoo and F. Harary, Step graphs, J. Combin. Inform. System Sci. 5 (1980) 52-53. 
  6. [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. [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. [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. [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. [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. [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. [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. [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. [14] M. Pfützenreuter, Konkurrenzgraphen von ungerichteten Graphen (Bachelor thesis, University of Lübeck, 2006). 
  15. [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. [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. [17] P. Schweitzer (Max-Planck-Institute for Computer Science, Saarbrücken, Germany), unpublished script (2010). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.