Vecindad (teoría de grafos)

Un grafo de 6 vértices y 7 aristas

En teoría de grafos, un vértice adyacente de un vértice v en un grafo es un vértice que está conectado a v mediante una arista. La vecindad de un vértice v en un grafo G es el subgrafo inducido de G que está formado por todos los vértices adyacentes y todas las aristas que conectan dichos vértices. Por ejemplo, la imagen muestra un grafo de 6 vértices y 7 aristas. El vértice 5 es adyacente a los vértices 1, 2, y 4, pero no es adyacente a los vértices 3 y 6. La vecindad del vértice 5 es el grafo con 3 vértices, 1, 2, y 4, y una arista conectando los vértices 1 y 2.

La vecindad es frecuentemente denotada N_G(v) o (cuando el grafo no es ambiguo) N(v). La misma notación también puede referirse a los conjuntos de vértices adyacentes en lugar de al correspondiente subgrafo. La vecindad descrita anteriormente no incluye al mismo v, y es mas específico referirse como la vecindad abierta de v; también es posible definir una vecindad donde v este incluido, llamada la vecindad cerrada y denotada por N_G[v]. Cuando aparece sin especificar, la vecindad se presume abierta.

Referencias

• Hartsfeld, N.; Ringel, G. (1991). «Clean triangulations». Combinatorica 11:  pp. 145–155. doi:10.1007/BF01206358. 

• Hell, Pavol (1978). «Graphs with given neighborhoods I». Colloque internationaux C.N.R.S., No. 260, Problems Combinatories et theorie des graphes. pp. 219–223. 

• Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002). «Whitney triangulations, local girth and iterated clique graphs». Discrete Mathematics 258:  pp. 123–135. doi:10.1016/S0012-365X(02)00266-2. http://xamanek.izt.uam.mx/map/papers/cuello10_DM.ps. 

• Malnič, Aleksander; Mohar, Bojan (1992). «Generating locally cyclic triangulations of surfaces». Journal of Combinatorial Theory, Series B 56 (2):  pp. 147–164. doi:10.1016/0095-8956(92)90015-P. 

• Sedlacek, J. (1983). «On local properties of finite graphs». Graph Theory, Lagów. Lecture Notes in Mathematics, no. 1018, Springer-Verlag. pp. 242–247. 

• Seress, Ákos; Szabó, Tibor (1995). «Dense graphs with cycle neighborhoods». Journal of Combinatorial Theory, Series B 63:  pp. 281–293. doi:10.1006/jctb.1995.1020. http://www.inf.ethz.ch/personal/szabo/PS/kornyezetek.ps. 

• Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM 30 (4):  pp. 729–735. doi:10.1145/2157.2158.