Familia de Petersen
En teoría de grafos, la familia de Petersen es un conjunto de siete grafos que incluye el grafo de Petersen y el grafo completo K6. Lleva el nombre del matemático danés Julius Petersen.
Cualquiera de los grafos de la familia de Petersen puede transformarse en cualquier otro grafo 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 grafos forman los menores prohibidos para los grafos embebidos sin enlaces, grafos que se pueden incrustar en el espacio tridimensional de tal manera que no hay dos ciclos en el grafo que estén enlazados.[1] También se encuentran entre los menores prohibidos para los grafos YΔY-reducibles.[2][3]
Definición editar
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 K6 de seis vértices, el grafo de ocho vértices formado al eliminar una sola arista del grafo bipartito completo K4,4 y el grafo tripartito completo de siete vértices K3,3,1.
Menores prohibidos editar
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 K5 ni un grafo bipartito completo K3,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 K4 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 K1,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]
Referencias editar
- ↑ a b Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), «Linkless embeddings of graphs in 3-space», Bulletin of the American Mathematical Society 28 (1): 84-89, MR 1164063, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5..
- ↑ a b c Truemper, Klaus (1992), Matroid Decomposition, Academic Press, pp. 100-101, archivado desde el original el 29 de agosto de 2017, consultado el 5 de septiembre de 2022..
- ↑ a b Yu, Yaming (2006), «More forbidden minors for wye-delta-wye reducibility», Electronic Journal of Combinatorics 13 (1): #R7..
- ↑ Sachs, Horst (1983), «On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem», en Horowiecki, M.; Kennedy, J. W.; Sysło, M. M., eds., Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics 1018, Springer-Verlag, pp. 230-241, doi:10.1007/BFb0071633..
Datos: Q3065962
Multimedia: Petersen family / Q3065962
