Familia de Petersen

Las formas de las transformaciones Δ-Y e Y-Δ utilizadas para definir la familia de Petersen es la siguiente:

• Si un grafo G contiene un vértice v con exactamente tres vecinos, entonces la transformada Y-Δ de G en v es el grafo formado al eliminar v de G y agregar aristas entre cada par de sus tres vértices vecinos.
• Si un grafo H contiene un triángulo uvw, entonces la transformada Δ-Y de H en uvw es el grafo formado al eliminar las aristas uv, vw y uw de H y agregar un nuevo vértice conectado a los tres vértices vecinos u, v y w.

Estas transformaciones se llaman así por la forma Δ de un triángulo en un grafo y la forma Y de un vértice de grado tres. Aunque estas operaciones en principio pueden conducir a multigrafos, esto no sucede dentro de la familia de Petersen. Debido a que estas operaciones conservan el número de aristas en un grafo, solo hay un número finito de grafos o multigrafos que se pueden formar a partir de un solo grafo inicial G mediante combinaciones de transformadas Δ-Y e Y-Δ.

La familia de Petersen consta entonces de cada grafo al que se puede llegar desde el grafo de Petersen mediante una combinación de transformadas Δ-Y e Y-Δ. Hay siete grafos en la familia, incluido el grafo completo K₆ de seis vértices, el grafo de ocho vértices formado al eliminar una sola arista del grafo bipartito completo K_4,4 y el grafo tripartito completo de siete vértices K_3,3,1.

Un menor de un grafo G es otro grafo formado a partir de G contrayendo y eliminando 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 grafos planos son exactamente aquellos que no tienen un grafo completo K₅ ni un grafo bipartito completo K_3,3 como menores.

Neil Robertson, Paul Seymour y Robin Thomas usaron la familia de Petersen como parte de una caracterización similar del embebido sin enlaces de grafos, incrustaciones de un grafo dado en el espacio euclídeo de tal manera que cada ciclo en el grafo es el límite de un disco que no está cruzado por ninguna otra parte del grafo.^[1] Horst Sachs había estudiado previamente tales incrustaciones, y demostró que los siete grafos de la familia de Petersen no tienen tales incrustaciones, planteando la cuestión de caracterizar los grafos embebibles sin enlaces mediante subgrafos prohibidos.^[4] Robertson et al. resolvieron la pregunta de Sachs al mostrar que los grafos embebibles sin enlaces son exactamente aquellos que no tienen a un miembro de la familia de Petersen como menor.

La familia de Petersen también forma algunos de los menores prohibidos para otra familia de grafos, los grafos reducibles YΔY. Un grafo conexo es YΔY-reducible si puede reducirse a un solo vértice mediante una secuencia de pasos, cada uno de los cuales es una transformación Δ-Y o Y-Δ, la eliminación de un autobucle o de una adyacencia múltiple, la eliminación de un vértice con un vecino, y la sustitución de un vértice de grado dos y sus dos aristas vecinas por una sola arista. Por ejemplo, el grafo completo K₄ se puede reducir a un solo vértice mediante una transformada Y-Δ que lo convierte en un triángulo con aristas duplicadas, la eliminación de las tres aristas duplicadas, una transformada Δ-Y que lo convierte en una garra K_1,3, y la eliminación de los tres vértices de grado uno de la garra. Cada uno de los grafos de la familia de Petersen es un prohibido menor mínimo para la familia de grafos reducibles YΔY.^[2] Sin embargo, Neil Robertson proporcionó un ejemplo de un grafo de ápice (un grafo embebible sin enlaces formado al agregar un vértice a un grafo plano) que no es reducible mediante la transformación YΔY, lo que demuestra que los grafos reducibles mediante YΔY forman una subclase propia de los grafos embebibles sin enlaces y tener menores prohibidos adicionales.^[2] De hecho, como mostró Yaming Yu, hay al menos 68.897.913.652 menores prohibidos para los grafos reducibles YΔY más allá de los siete de la familia de Petersen.^[3]