En el campo matemático de la teoría de grafos , un grafo prismático es un grafo que tiene uno de los prismas como esqueleto.
Los gráficos individuales pueden denominarse según el sólido asociado:
Aunque geométricamente los polígonos estrellados también forman las caras de una secuencia diferente de poliedros prismáticos (autointersecantes y no convexos), los gráficos de estos prismas estrellados son isomorfos a los gráficos prismáticos y no forman una secuencia separada de gráficos.
Los grafos prismáticos son ejemplos de grafos de Petersen generalizados , con parámetros GP( n ,1). También pueden construirse como el producto cartesiano de un grafo cíclico con una sola arista. [1]
Al igual que muchos grafos transitivos de vértice, los grafos prismáticos también pueden construirse como grafos de Cayley . El grupo diedro de orden n es el grupo de simetrías de un n -gono regular en el plano; actúa sobre el n -gono mediante rotaciones y reflexiones. Puede generarse mediante dos elementos, una rotación de un ángulo de 2 π / n y una única reflexión, y su grafo de Cayley con este conjunto generador es el grafo prismático. De manera abstracta, el grupo tiene la presentación (donde r es una rotación y f es una reflexión o volteo) y el grafo de Cayley tiene r y f (o r , r −1 y f ) como sus generadores. [1]
Los gráficos de prismas n -gonales con valores impares de n pueden construirse como gráficos circulantes . Sin embargo, esta construcción no funciona para valores pares de n . [1]
El grafo de un prisma n -gonal tiene 2 n vértices y 3 n aristas. Son grafos cúbicos regulares . Como el prisma tiene simetrías que llevan cada vértice a cada vértice, los grafos prismáticos son grafos transitivos de vértice . Como grafos poliédricos , también son grafos planos con 3 vértices conexos . Todo grafo prismático tiene un ciclo hamiltoniano . [2]
Entre todos los grafos cúbicos biconexos , los grafos prismáticos tienen dentro de un factor constante el mayor número posible de factorizaciones 1. Una factorización 1 es una partición del conjunto de aristas del grafo en tres emparejamientos perfectos, o equivalentemente una coloración de las aristas del grafo con tres colores. Todo grafo cúbico biconexo de n vértices tiene O (2 n /2 ) factorizaciones 1, y los grafos prismáticos tienen Ω (2 n /2 ) factorizaciones 1. [3]
El número de árboles de expansión de un gráfico de prisma n -gonal se da mediante la fórmula [4]
Para n = 3, 4, 5, ... estos números son
Los gráficos de prismas n -gonales para valores pares de n son cubos parciales . Forman una de las pocas familias infinitas conocidas de cubos parciales cúbicos y (excepto cuatro ejemplos esporádicos) los únicos cubos parciales cúbicos transitivos por vértices. [5]
El prisma pentagonal es uno de los menores prohibidos para los gráficos de ancho de árbol tres. [6] El prisma triangular y el gráfico cúbico tienen ancho de árbol exactamente tres, pero todos los gráficos de prismas más grandes tienen ancho de árbol cuatro.
Otras secuencias infinitas de grafos poliédricos formados de manera similar a partir de poliedros con bases de polígonos regulares incluyen los grafos de antiprismas (grafos de antiprismas ) y los grafos de rueda (grafos de pirámides ). Otros grafos poliédricos transitivos por vértices incluyen los grafos de Arquímedes .
Si los dos ciclos de un grafo prismático se rompen mediante la eliminación de una única arista en la misma posición en ambos ciclos, el resultado es un grafo en escalera . Si estas dos aristas eliminadas se reemplazan por dos aristas cruzadas, el resultado es un grafo no plano llamado escalera de Möbius . [7]
