En la teoría de grafos, una familia de grafos de Petersen es un conjunto de siete grafos no dirigidos , incluido el grafo de Petersen y el grafo completo K 6 . La familia Petersen lleva el nombre del matemático danés Julius Petersen porque el gráfico de Petersen está incluido en el conjunto.
Cualquiera de los gráficos de la familia Petersen se puede transformar en cualquier otro gráfico de la familia Δ-Y o Y-Δ mediante transformaciones , operaciones en las que se reemplaza un triángulo por un vértice de grado 3, o viceversa. Estos siete gráficos forman menores prohibidos para gráficos incrustables no vinculados , gráficos que pueden incrustarse en un espacio tridimensional de tal manera que no hay dos ciclos que formen un vínculo (en el sentido de la teoría de nudos) [1] . También se encuentran entre los menores prohibidos de los gráficos reducibles YΔY [2] [3] .
Las transformaciones Δ-Y e Y-Δ utilizadas en la definición de la familia Petersen son las siguientes:
Estas transformaciones se llaman así porque el símbolo Δ parece un triángulo y el símbolo Y parece un vértice con tres aristas. Si bien estas operaciones podrían, en principio, conducir a multigrafos , no lo hacen en la familia Petersen. Dado que estas operaciones conservan el número de aristas en el gráfico, solo se puede formar un número finito de gráficos o multigráficos a partir de un solo gráfico inicial G mediante una combinación de transformaciones Δ-Y e Y-Δ.
La familia de Petersen consta de todos los gráficos que se pueden obtener del gráfico de Petersen mediante una combinación de las transformaciones Δ-Y e Y-Δ. Hay siete gráficos en la familia, e incluye un gráfico completo K 6 con seis vértices, un gráfico de ocho vértices formado quitando un borde de un gráfico bipartito completo K 4,4 y un gráfico tripartito completo con siete vértices K 3 ,3,1 .
Un menor de un grafo G es otro grafo formado a partir de un grafo G contrayendo y quitando aristas. Como muestra el teorema de Robertson-Seymour , muchas familias importantes de grafos se pueden caracterizar por un conjunto finito de menores prohibidos . Por ejemplo, según el teorema de Wagner , los gráficos planos son exactamente los gráficos que no contienen ni el gráfico completo K 5 ni el gráfico bipartito completo K 3,3 como menores .
Neil Robertson Paul Seymour y Robin Thomas utilizaron la familia Petersen como parte de una caracterización similar degrafos incrustables no vinculados , es decir, gráficos que se pueden incrustar en el espacio euclidiano de tal manera que cualquier ciclo en el gráfico es el límite de un disco (topológico) que no se cruza con ninguna otra parte del gráfico [1] . Sachs Horst estudió tales incrustaciones antes y mostró que siete gráficos de la familia Petersen no tienen tales incrustaciones, y planteó la cuestión de caracterizar gráficos con incrustaciones no vinculadas enumerando subgrafos prohibidos [4] . Robertson y otros resolvieron la pregunta de Sachs mostrando que los gráficos integrables sin enlaces son exactamente aquellos gráficos que no tienen a miembros de la familia Petersen como menores.
Los grafos de la familia Petersen se incluyen en los menores prohibidos de otra familia de grafos, los grafos reducibles YΔY. Un gráfico conectado es YΔY-reducible si se puede transformar en un solo vértice mediante una secuencia de pasos, cada uno de los cuales es una transformación Δ-Y o Y-Δ, eliminando un bucle o borde múltiple, eliminando un vértice con un solo vecino , y reemplazando un vértice de grado dos y dos costillas adyacentes por una costilla. Por ejemplo, un gráfico K 4 completo se puede reducir a un solo vértice mediante la transformación Y-Δ, que lo convierte en un triángulo con aristas dobles. Después de eliminar tres aristas dobles, transformar Δ-Y, lo que transforma el triángulo en una garra (tres aristas con un vértice común) K 1,3 , y eliminar los vértices colgantes de la garra, el gráfico se convierte en un vértice. Cada uno de los grafos de la familia Petersen forma el mínimo prohibido menor para la familia de grafos reducibles YΔY [2] . Sin embargo, Neil Robertson da un ejemplo de un gráfico de vértices (un gráfico incrustable sin enlaces formado al agregar un vértice a un gráfico plano) que no es reducible por YΔY. Esto muestra que los gráficos reducibles YΔY forman su propia subclase de gráficos incrustables sin enlaces, pero, además de los gráficos de la familia Petersen, tienen menores prohibidos adicionales [2] . De hecho, como ha demostrado Yaming Yu, hay al menos 68.897.913.652 menores prohibidos para grafos reducibles YΔY, además de los siete grafos de la familia Petersen [3] .