Vecindario (teoría de grafos)

En este grafo, los vértices adyacentes a 5 son 1, 2 y 4. El vecindario de 5 es el grafo que consiste en los vértices 1, 2, 4 y la arista que une 1 y 2.

En teoría de grafos , un vértice adyacente a un vértice $v$ en un grafo es un vértice que está conectado a $v$ por una arista . La vecindad de un vértice $v$ en un grafo $G$ es el subgrafo de $G$ inducido por todos los vértices adyacentes a $v$ , es decir, el grafo compuesto por los vértices adyacentes a $v$ y todas las aristas que conectan los vértices adyacentes a $v$ .

El vecindario se denota a menudo como ⁠ ⁠ $Estilo de visualización N_{G}(v)$ o (cuando el grafo no es ambiguo) ⁠ ⁠ ${\estilo de visualización N(v)}$ . La misma notación de vecindario también se puede usar para referirse a conjuntos de vértices adyacentes en lugar de los subgrafos inducidos correspondientes. El vecindario descrito anteriormente no incluye al propio $v$ , y es más específicamente el vecindario abierto de $v$ ; también es posible definir un vecindario en el que se incluye al propio $v , llamado$ vecindario cerrado y denotado por ⁠ ⁠ $Estilo de visualización N_{G}[v]}$ . Cuando se establece sin ninguna calificación, se supone que un vecindario es abierto.

Los vecindarios se pueden utilizar para representar grafos en algoritmos informáticos, a través de representaciones de listas de adyacencia y matrices de adyacencia . Los vecindarios también se utilizan en el coeficiente de agrupamiento de un grafo, que es una medida de la densidad media de sus vecindarios. Además, muchas clases importantes de grafos se pueden definir por las propiedades de sus vecindarios o por simetrías que relacionan los vecindarios entre sí.

Un vértice aislado no tiene vértices adyacentes. El grado de un vértice es igual al número de vértices adyacentes. Un caso especial es un bucle que conecta un vértice consigo mismo; si existe tal arista, el vértice pertenece a su propia vecindad.

Propiedades locales en gráficos

Si todos los vértices en G tienen vecindarios que son isomorfos al mismo grafo H , se dice que G es localmente H , y si todos los vértices en G tienen vecindarios que pertenecen a alguna familia de grafos F , se dice que G es localmente F . ^[1] Por ejemplo, en el grafo octaédrico , que se muestra en la figura, cada vértice tiene un vecindario isomorfo a un ciclo de cuatro vértices, por lo que el octaedro es localmente C ₄ .

Por ejemplo:

Cualquier grafo completo K _n es localmente K _n-1 . Los únicos grafos que son localmente completos son las uniones disjuntas de grafos completos.
Un grafo de Turán T ( rs , r ) es localmente T (( r -1) s , r -1). De manera más general, cualquier gráfico de Turán es localmente Turán.
Todo grafo plano es localmente exteriormente plano . Sin embargo, no todo grafo localmente exteriormente plano es plano.
Un gráfico está libre de triángulos si y sólo si es localmente independiente .
Todo grafo k - cromático es localmente ( k -1)-cromático. Todo grafo k -cromático localmente tiene número cromático . ^[2] $O({\sqrt {kn}})$
Si una familia de grafos F está cerrada bajo la operación de tomar subgrafos inducidos, entonces cada grafo en F es también localmente F . Por ejemplo, cada grafo cordal es localmente cordal; cada grafo perfecto es localmente perfecto; cada grafo de comparabilidad es localmente comparable; cada grafo (k)-(ultra)-homogéneo es localmente (k)-(ultra)-homogéneo.
Un grafo es localmente cíclico si cada vecindad es un ciclo . Por ejemplo, el octaedro es el único grafo conexo localmente C _{4 , el}icosaedro es el único grafo conexo localmente C ₅ , y el grafo de Paley de orden 13 es localmente C ₆ . Los grafos localmente cíclicos distintos de K ₄ son exactamente los grafos subyacentes de las triangulaciones de Whitney , incrustaciones de grafos en superficies de tal manera que las caras de la incrustación son las camarillas del grafo. ^[3] Los grafos localmente cíclicos pueden tener tantas como aristas. ^[4] $estilo de visualización n^{2-o(1)}}$
Los grafos sin garras son los grafos que son localmente co- libres de triángulos ; es decir, para todos los vértices, el grafo complementario del entorno del vértice no contiene un triángulo. Un grafo que es localmente H es libre de garras si y solo si el número de independencia de H es como máximo dos; por ejemplo, el grafo del icosaedro regular es libre de garras porque es localmente C ₅ y C ₅ tiene número de independencia dos.
Los gráficos localmente lineales son los gráficos en los que cada vecindad es una correspondencia inducida . ^[5]
Los gráficos de Johnson están cuadriculados localmente, lo que significa que cada vecindario es un gráfico de torre . ^[6]

Vecindario de un conjunto

Para un conjunto A de vértices, el vecindario de A es la unión de los vecindarios de los vértices, y por lo tanto es el conjunto de todos los vértices adyacentes a al menos un miembro de A.

Se dice que un conjunto A de vértices en un grafo es un módulo si cada vértice en A tiene el mismo conjunto de vecinos fuera de A. Cualquier grafo tiene una descomposición recursiva única en módulos, su descomposición modular , que se puede construir a partir del grafo en tiempo lineal ; los algoritmos de descomposición modular tienen aplicaciones en otros algoritmos de grafos, incluido el reconocimiento de grafos de comparabilidad .

Véase también

Manta de Markov
Barrio Moore
Barrio de Von Neumann
Segundo problema del barrio
Figura de vértice , un concepto relacionado en los poliedros
Enlace (complejo simplicial) , una generalización de la vecindad a complejos simpliciales

Notas

^ El infierno 1978, Sedláček 1983
^ Wigderson 1983.
^ Hartsfeld y Ringel 1991; Larrión, Neumann-Lara & Pizaña 2002; Malnič y Mohar 1992
^ Seress y Szabó 1995.
^ Fronček 1989.
^ Cohen 1990.

Referencias

Cohen, Arjeh M. (1990), "Reconocimiento local de grafos, edificios y geometrías relacionadas" (PDF) , en Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Geometrías finitas, edificios y temas relacionados: artículos de la Conferencia sobre edificios y geometrías relacionadas celebrada en Pingree Park, Colorado, del 17 al 23 de julio de 1988 , Oxford Science Publications, Oxford University Press, págs. 85–94, MR 1072157; véanse en particular las páginas 89-90
Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3–6, hdl :10338.dmlcz/136481, MR 1016323
Hartsfeld, Nora; Ringel, Gerhard (1991), "Triangulaciones limpias", Combinatorica , 11 (2): 145–155, doi :10.1007/BF01206358, S2CID 28144260.
Hell, Pavol (1978), "Gráficos con vecindades dadas I", Problèmes combinatoires et théorie des graphes , Colloques internationaux CNRS, vol. 260, págs. 219-223.
Larrión, F.; Neumann-Lara, V. ; Pizaña, MA (2002), "Triangulaciones de Whitney, circunferencia local y grafos de clique iterados", Discrete Mathematics , 258 (1–3): 123–135, doi : 10.1016/S0012-365X(02)00266-2.
Malnič, Aleksander; Mohar, Bojan (1992), "Generación de triangulaciones cíclicas locales de superficies", Journal of Combinatorial Theory, Serie B , 56 (2): 147–164, doi :10.1016/0095-8956(92)90015-P.
Sedláček, J. (1983), "Sobre las propiedades locales de los grafos finitos", Graph Theory, Lagów , Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 242–247, doi :10.1007/BFb0071634, ISBN 978-3-540-12687-4.
Seress, Ákos; Szabó, Tibor (1995), "Gráficos densos con vecindarios cíclicos", Journal of Combinatorial Theory, Serie B , 63 (2): 281–293, doi : 10.1006/jctb.1995.1020.
Wigderson, Avi (1983), "Mejora de la garantía de rendimiento para la coloración aproximada de gráficos", Journal of the ACM , 30 (4): 729–735, doi : 10.1145/2157.2158 , S2CID 32214512.