En matemáticas teóricas de grafos , un grafo estrangulado es un grafo en el que eliminar los bordes de cualquier ciclo inducido de longitud mayor que tres desconectaría el grafo restante. Es decir, son las gráficas en las que cada ciclo periférico es un triángulo.
Ejemplos de
En un gráfico plano máximo , o más generalmente en cada gráfico poliédrico , los ciclos periféricos son exactamente las caras de una incrustación plana del gráfico, por lo que un gráfico poliédrico se estrangula si y solo si todas las caras son triángulos, o equivalentemente es máximo. planar. Cada gráfico de cuerdas está estrangulado, porque los únicos ciclos inducidos en los gráficos de cuerdas son triángulos, por lo que ya no hay ciclos para eliminar.
Caracterización
Se forma una suma de clique de dos gráficos identificando dos cliques de igual tamaño en cada gráfico, y luego posiblemente eliminando algunos de los bordes de clique. Para la versión de sumas de clique relevantes para gráficos estrangulados, se omite el paso de eliminación de borde. Una clique-suma 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 o al otro (de lo contrario, tendría una cuerda entre los vértices en los que cruzó desde uno). lado de la suma al otro), y las partes desconectadas de ese lado formado al eliminar el ciclo deben permanecer desconectadas en la clique-sum. Cada grafo cordal puede descomponerse de esta manera en una suma de gráficos completos de clique , y cada gráfico plano máximo se puede descomponer en una suma de clique de gráficos planos máximos conectados de 4 vértices .
Como muestran Seymour y Weaver (1984) , estos son los únicos bloques de construcción posibles de las gráficas estranguladas: las gráficas estranguladas son exactamente las gráficas que pueden formarse como clique-sumas de gráficas completas y gráficas planas máximas.
Ver también
- Gráfico de línea perfecta , un gráfico en el que cada ciclo impar es un triángulo
Referencias
- Seymour, PD ; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.