Diferencia entre revisiones de «Familia de Petersen»
Creación de «Familia de Petersen» |
(Sin diferencias)
|
Revisión del 18:38 5 sep 2022
En teoría de grafos, la familia Petersen es un conjunto de siete grafo que incluye el Grafo de Petersen y el grafo completo K6. La familia Petersen lleva el nombre del matemático danés Julius Petersen, epónimo del grafo de Petersen.
Cualquiera de los grafos de la familia Petersen puede transformarse en cualquier otro grafo de la familia mediante Δ-Y or Y-Δ transforms, operaciones en las que un triángulo se reemplaza por un vértice de grado tres o viceversa. Estos siete grafos forman los forbidden minor para linklessly embeddable graphs, grafos que se pueden incrustar en el espacio tridimensional de tal manera que no hay dos ciclos en el grafo que sean linked.[1] También se encuentran entre los menores prohibidos para el YΔY-reducible graphs.[2][3]
Definición
La forma de Δ-Y and Y-Δ transforms utilizada para definir la familia 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 vecinos.
- Si un grafo H contiene un triángulo uvw, entonces la transformada Δ-Y de H en uvw es el grafo formado al eliminar los bordes uv, vw y uw de H y agregar un nuevo vértice conectado a los tres 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 multigrafo, eso no sucede dentro de la familia 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 Petersen consta entonces de cada grafo al que se puede llegar desde Grafo de Petersen mediante una combinación de transformadas Δ-Y e Y-Δ. Hay siete grafos en la familia, incluido el grafo completo K6 en seis vértices, el grafo de ocho vértices formado al eliminar un solo borde del grafo bipartito completo K4,4 y el grafo tripartito completo de siete vértices K3,3,1.
Menores prohibidos
Un menor de un grafo G es otro grafo formado a partir de G contrayendo y eliminando aristas. Como muestra Robertson–Seymour theorem, muchas familias importantes de grafos se pueden caracterizar por un conjunto finito de forbidden minor: por ejemplo, según Wagner's theorem, los grafo plano son exactamente los grafos que no tienen grafo completo K5 ni grafo bipartito completo K 3,3 como menores.
Neil Robertson, Paul Seymour y Robin Thomas usaron la familia Petersen como parte de una caracterización similar de embebido sin enlace de grafos, incrustaciones de un grafo dado en Espacio euclídeo de tal manera que cada cycle en el grafo es el límite de un disco que no está cruzado por ningún otro. otra parte del grafo.[1] Horst Sachs había estudiado previamente tales incrustaciones, mostró que los siete grafos de la familia Petersen no tienen tales incrustaciones y planteó la cuestión de caracterizar los grafos incrustables sin enlaces mediante subgrafos prohibidos.[4] Robertson et al. resolvió la pregunta de Sachs al mostrar que los grafos incrustables sin enlaces son exactamente los grafos que no tienen a un miembro de la familia Petersen como menor.
La familia 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 transformada Δ-Y o Y-Δ, la eliminación de un autobucle 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 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 el claw K1,3, y eliminación de los tres vértices de grado uno de la garra. Cada uno de los grafos de la familia Petersen forma un mínimo prohibido menor para la familia de grafos reducibles YΔY.[2] Sin embargo, Neil Robertson proporcionó un ejemplo de un apex graph (un grafo incrustable sin enlaces formado al agregar un vértice a un grafo plano) que no es reducible con YΔY, lo que muestra que los grafos reducibles con YΔY forman una subclase adecuada de los grafos incrustables 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 Petersen.[3]
Referencias
- ↑ 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..
- ↑ 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..
| Control de autoridades |
|
|---|
Datos: Q3065962
Multimedia: Petersen family / Q3065962