Gráfico estrangulado

En matemáticas de teoría de grafos , un grafo estrangulado es aquel en el que eliminar las aristas de cualquier ciclo inducido de longitud mayor que tres desconectaría el grafo restante. Es decir, son los grafos en los que cada ciclo periférico es un triángulo.

En un grafo planar maximal , o más generalmente en cualquier grafo poliédrico , los ciclos periféricos son precisamente las caras de una incrustación planar del grafo, por lo que un grafo poliédrico está estrangulado si y solo si todas sus caras son triángulos, o equivalentemente, es planar maximal. Todo grafo cordal está estrangulado, porque los únicos ciclos inducidos en los grafos cordales son triángulos, por lo que ya no hay ciclos que eliminar.

Una suma de cliques de dos grafos se forma identificando dos cliques de igual tamaño en cada grafo y, posiblemente, eliminando algunas de las aristas de los cliques. Para la versión de sumas de cliques relevante para grafos estrangulados, se omite el paso de eliminación de aristas. Una suma de cliques de este tipo entre dos grafos estrangulados da como resultado otro grafo estrangulado, ya que cada ciclo inducido largo en la suma debe estar confinado a un lado u otro (de lo contrario, tendría una cuerda entre los vértices en los que cruza de un lado de la suma al otro), y las partes desconectadas de ese lado formadas al eliminar el ciclo deben permanecer desconectadas en la suma de cliques. Todo grafo cordal puede descomponerse de esta manera en una suma de cliques de grafos completos , y todo grafo planar maximal puede descomponerse en una suma de cliques de grafos planares maximales con 4 vértices conectados .

Como muestran Seymour y Weaver (1984) , estos son los únicos bloques de construcción posibles de los grafos estrangulados: los grafos estrangulados son exactamente los grafos que se pueden formar como sumas de cliques de grafos completos y grafos planares máximos.

• Gráfico de línea perfecta , un gráfico en el que cada ciclo impar es un triángulo.

• Seymour, PD ; Weaver, RW (1984), "Una generalización de los grafos cordales", Journal of Graph Theory , 8 (2): 241–251 , doi : 10.1002/jgt.3190080206 , MR 0742878 .