En teoria de grafos, la família de Petersen és un conjunt de sèt grafos que inclou el grafo de Petersen i el grafo complet K6. Du el nom del matemàtic danés Julius Petersen.

La família de Petersen. K6 està en la part superior de l'ilustració i el grafo de Petersen està en la part inferior. Els enllaços blaus indiquen les transformades Δ-I o Y-Δ entre els grafos de la família

Qualsevol dels grafos de la família de Petersen pot transformar-se en qualsevol atre grafo de la família per mig de transformacions Δ-I o Y-Δ, operacions en les que un triàngul es reemplaça per un vèrtiç de grau tres o viceversa. Estos sèt grafos formen els menors prohibits per als grafos incrustats sense enllaços, grafos que es poden incrustar en l'espai tridimensional de tal manera que no hi ha dos cicles en el grafo que estiguen enllaçats.[1] També es troben entre els menors prohibits per als grafos IΔI-reducibles.[2][3]

Definició

Les formes de les transformacions Δ-I i Y-Δ utilisades per a definir la família de Petersen és la següent: Si un grafo G conté un vèrtiç v en exactament tres veïns, llavors la transformada Y-Δ de G en v és el grafo format en eliminar v de G i agregar arestes entre cada parell dels seus tres vèrtiços veïns. Si un grafo H conté un triàngul uvw, llavors la transformada Δ-I de H en uvw és el grafo format en eliminar les arestes uv, vw i uw de H i agregar un nou vèrtiç conectat als tres vèrtiços veïns o, v i w. Estes transformacions es diuen aixina per la forma Δ d'un triàngul en un grafo i la forma I d'un vèrtiç de grau tres. Encara que estes operacions en principi poden conduir a multigrafos, açò no succeïx dins de la família de Petersen. Degut a que estes operacions conserven el número d'arestes en un grafo, solament hi ha un número finit de grafos o multigrafos que es poden formar a partir d'un sol grafo inicial G per mig de combinacions de transformades Δ-I i Y-Δ.

La família de Petersen consta llavors de cada grafo al que es pot aplegar des del grafo de Petersen per mig d'una combinació de transformades Δ-I i Y-Δ. Hi ha sèt grafos en la família, inclós el grafo complet K6 de sis vèrtiços, el grafo de huit vèrtiços format en eliminar una sola aresta del grafo bipartit complet K4,4 i el grafo tripartit complet de sèt vèrtiços K3,3,1.

Menors prohibits

 
Grafo d'àpiç de Robertson irreducible, que mostra que els gràfics reducibles IΔI tenen menors prohibits adicionals ademés dels de la família de Petersen

Un menor d'un grafo G és un atre grafo format a partir de G contraent i eliminant arestes. Com a mostra el teorema de Robertson-Seymour, moltes famílies importants de grafos es poden caracterisar per un conjunt finit de menors prohibits: per eixemple, segons el teorema de Wagner, els grafos plans són exactament aquells que no tenen un grafo complet K5 ni un grafo bipartit complet K3,3 com a menors.


Neil Robertson, Paul Seymour i Robin Thomas varen usar la família de Petersen com a part d'una caracterisació similar de l'incrustat sense enllaços de grafos, incrustacions d'un grafo donat en l'espai euclidià de tal manera que cada cicle en el grafo és el llímit d'un disc que no està creuat per cap atra part del grafo.[1] Horst Sachs havia estudiat prèviament tals incrustacions, i va demostrar que els sèt grafos de la família de Petersen no tenen tals incrustacions, plantejant la qüestió de caracterisar els grafos embebibles sense enllaços per mig de subgrafos prohibits.[4] Robertson et al. varen resoldre la pregunta de Sachs en mostrar que els grafos embebibles sense enllaços són exactament aquells que no tenen a un membre de la família de Petersen com a menor.

La família de Petersen també forma alguns dels menors prohibits per a una atra família de grafos, els grafos reducibles IΔY. Un grafo conexo és IΔI-reducible si pot reduir-se a un sol vèrtiç per mig d'una seqüència de passos, cada u dels quals és una transformació Δ-I o Y-Δ, l'eliminació d'un autobucle o d'una adyacencia múltiple, l'eliminació d'un vèrtiç en un veí, i la substitució d'un vèrtiç de grau dos i les seues dos arestes veïnes per una sola aresta. Per eixemple, el grafo complet K4 es pot reduir a un sol vèrtiç per mig d'una transformada Y-Δ que ho convertix en un triàngul en arestes duplicades, l'eliminació de les tres arestes duplicades, una transformada Δ-I que ho convertix en una garra K1,3, i l'eliminació dels tres vèrtiços de grau un de la garra. Cada u dels grafos de la família de Petersen és un prohibit menor mínim per a la família de grafos reducibles IΔY.[2] No obstant, Neil Robertson va proporcionar un eixemple d'un grafo d'àpiç (un grafo embebible sense enllaços format en agregar un vèrtiç a un grafo pla) que no és reducible per mig de la transformació IΔI, lo que demostra que els grafos reducibles per mig d'IΔI formen una subclasse pròpia dels grafos embebibles sense enllaços i tindre menors prohibits adicionals.[2] De fet, com va mostrar Yaming Yu, hi ha a lo manco 68.897.913.652 menors prohibits per als grafos reducibles IΔI més allà dels sèt de la família de Petersen.[3]

Referències

  1. ↑ 1,0 1,1 .
  2. ↑ 2,0 2,1 2,2 .
  3. ↑ 3,0 3,1 .
  4. ↑ .