En teoría de grafos , la familia Petersen es un conjunto de siete grafos no dirigidos que incluye el grafo de Petersen y el grafo completo K 6 . La familia Petersen lleva el nombre del matemático danés Julius Petersen , homónimo del gráfico de Petersen.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/0/04/Petersen_family.svg/300px-Petersen_family.svg.png)
Cualquiera de los gráficos de la familia Petersen se puede transformar en cualquier otro gráfico de la familia mediante transformaciones Δ-Y o Y-Δ , operaciones en las que un triángulo se reemplaza por un vértice de grado tres o viceversa. Estos siete gráficos forman los menores prohibidos para gráficos incrustables sin enlaces , gráficos que se pueden incrustar en un espacio tridimensional de tal manera que no hay dos ciclos en el gráfico vinculados . [1] También se encuentran entre los menores prohibidos para los gráficos YΔY-reducibles . [2] [3]
Definición
La forma de las transformadas Δ-Y e Y-Δ que se utilizan para definir la familia Petersen es la siguiente:
- Si un gráfico G contiene un vértice v con exactamente tres vecinos, entonces la transformada Y-Δ de G en v es el gráfico formado al eliminar v de G y agregar aristas entre cada par de sus tres vecinos.
- Si una gráfica H contiene un triángulo uvw , entonces la transformada Δ-Y de H en uvw es la gráfica formada al eliminar las aristas uv , vw y uw de H y agregar un nuevo vértice conectado a los tres u , v y w .
Estas transformaciones se denominan así debido a la forma Δ de un triángulo en un gráfico y la forma Y de un vértice de grado tres. Aunque estas operaciones pueden, en principio, dar lugar a gráficos múltiples , eso no ocurre dentro de la familia Petersen. Debido a que estas operaciones conservan el número de aristas en un gráfico, solo hay un número finito de gráficos o multigrafos que se pueden formar a partir de un solo gráfico inicial G mediante combinaciones de transformadas Δ-Y e Y-Δ.
Luego, la familia Petersen consta de todos los gráficos que se pueden alcanzar desde el gráfico de Petersen mediante una combinación de transformadas Δ-Y e Y-Δ. Hay siete gráficos en la familia, incluido el gráfico completo K 6 en seis vértices, el gráfico de ocho vértices formado al eliminar un solo borde del gráfico bipartito completo K 4,4 y el gráfico tripartito completo de siete vértices K 3, 3,1 .
Menores prohibidos
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/7e/Apex_rhombic_dodecahedron.svg/220px-Apex_rhombic_dodecahedron.svg.png)
Un menor de un gráfico G es otro gráfico formado a partir de G al contraer y eliminar los bordes. Como muestra el teorema de Robertson-Seymour , muchas familias importantes de gráficas se pueden caracterizar por un conjunto finito de menores prohibidos : por ejemplo, según el teorema de Wagner , las gráficas planas son exactamente las gráficas que no tienen ni la gráfica completa K 5 ni la gráfica completa. grafo bipartito K 3,3 como menores.
Neil Robertson , Paul Seymour y Robin Thomas utilizaron la familia Petersen como parte de una caracterización similar de incrustaciones de gráficos sin enlaces , incrustaciones de un gráfico dado en el espacio euclidiano de tal manera que cada ciclo en el gráfico es el límite de un disco que no está cruzado por ninguna otra parte del gráfico. [1] Horst Sachs había estudiado previamente tales incrustaciones, mostró que los siete gráficos de la familia Petersen no tienen tales incrustaciones, y planteó la cuestión de caracterizar los gráficos incrustables sin enlaces mediante subgrafos prohibidos. [4] Robertson y col. resolvió la pregunta de Sachs mostrando que los gráficos integrables sin enlaces son exactamente los gráficos que no tienen un miembro de la familia Petersen como menor de edad.
La familia Petersen también forma algunos de los menores prohibidos para otra familia de gráficos, los gráficos YΔY-reducibles. Un gráfico conectado es YΔY-reducible si se puede reducir a un solo vértice mediante una secuencia de pasos, cada uno de los cuales es una transformada Δ-Y o Y-Δ, la eliminación de un bucle propio o 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 arista única. Por ejemplo, el gráfico completo K 4 se puede reducir a un solo vértice mediante una transformada Y-Δ que lo convierte en un triángulo con aristas duplicadas, eliminación de las tres aristas dobladas, una transformada Δ-Y que lo convierte en la garra K 1,3 , y eliminación de los vértices de tres grados uno de la garra. Cada uno de los gráficos de la familia Petersen forma un menor mínimo prohibido para la familia de gráficos YΔY reducibles. [2] Sin embargo, Neil Robertson proporcionó un ejemplo de un gráfico de vértice (un gráfico incrustable sin enlaces formado al agregar un vértice a un gráfico plano) que no es YΔY-reducible, lo que muestra que los gráficos YΔY-reducibles forman una subclase adecuada de linkless gráficos incrustables y tienen menores prohibidos adicionales. [2] De hecho, como mostró Yaming Yu, hay al menos 68,897,913,652 menores prohibidos para los gráficos reducibles YΔY más allá de los siete de la familia Petersen. [3]
Referencias
- ^ a b Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993), "Inserciones sin enlaces de gráficos en 3 espacios", Boletín de la Sociedad Americana de Matemáticas , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063.
- ^ a b c Truemper, Klaus (1992), Descomposición de matroides (PDF) , Academic Press, págs. 100–101.
- ^ a b Yu, Yaming (2006), "Más menores prohibidos para la reducibilidad estrella-delta-estrella" (PDF) , Electronic Journal of Combinatorics , 13 (1): # R7.
- ^ Sachs, Horst (1983), "Sobre un análogo espacial del teorema de Kuratowski sobre grafos planos - un problema abierto", en Horowiecki, M .; Kennedy, JW; Sysło, MM (eds.), Graph Theory: Actas de una conferencia celebrada en Łagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, págs. 230–241, doi : 10.1007 / BFb0071633.