Gráfico de prisma

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 su estructura básica.

Los gráficos individuales pueden recibir el nombre del sólido asociado:

• Grafo prismático triangular : 6 vértices, 9 aristas
• Grafo cúbico : 8 vértices, 12 aristas
• Grafo de prisma pentagonal : 10 vértices, 15 aristas
• Grafo de prisma hexagonal : 12 vértices, 18 aristas
• Grafo prismático heptagonal : 14 vértices, 21 aristas
• Grafo de prisma octogonal : 16 vértices, 24 aristas
• ...

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 de los prismas y no forman una secuencia de gráficos separada.

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értices, los grafos prisma también pueden construirse como grafos de Cayley . El grupo diedral 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 reflexión simple, y su grafo de Cayley con este conjunto generador es el grafo prisma. Abstractamente, el grupo tiene la presentación${\displaystyle \langle r,f\mid r^{n},f^{2},(rf)^{2}\rangle }$(donde r es una rotación y f es una reflexión o volteo) y el grafo de Cayley tiene a r y f (o r , r ^{− 1} y f ) como sus generadores. ^{[ 1 ]}

Los grafos prismáticos n -gonales con valores impares de n pueden construirse como grafos circulantes.${\displaystyle C_{2n}^{2,n}}$. 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 regulares y cúbicos . Dado que el prisma tiene simetrías que llevan cada vértice a cada otro vértice, los grafos del prisma son grafos transitivos de vértice . Como grafos poliédricos , también son grafos planares con 3 vértices conectados . Todo grafo de prisma tiene un ciclo hamiltoniano . ^{[ 2 ]} Los grafos de prisma de lados pares son grafos bipartitos .

Entre todos los grafos cúbicos biconectados , los grafos prismáticos poseen, dentro de un factor constante, el mayor número posible de 1-factorizaciones . Una 1-factorización 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 biconectado de n vértices tiene O (2n ^{/ 2} ) 1-factorizaciones, y los grafos prismáticos tienen Ω (2n ^{/ 2} ) 1-factorizaciones. ^{[ 3 ]}

El número de árboles de expansión de un grafo prismático n -gonal viene dado por la fórmula ^{[ 4 ].}

${\displaystyle {\frac {n}{2}}{\bigl (}(2+{\sqrt {3}})^{n}+(2-{\sqrt {3}})^{n}-2){\bigr .}}$

Para n = 3, 4, 5, ... estos números son

75, 384, 1805, 8100, 35287, 150528, ... (secuencia A006235 en el OEIS ) .

Los grafos prismáticos n -gonales para valores pares de n son cubos parciales . Forman una de las pocas familias infinitas conocidas de cubos parciales cúbicos y (salvo cuatro ejemplos esporádicos) son los únicos cubos parciales cúbicos transitivos en vértices. ^{[ 5 ]}

El prisma pentagonal es uno de los menores prohibidos para los grafos de ancho de árbol tres. ^{[ 6 ]} El prisma triangular y el grafo cúbico tienen un ancho de árbol exactamente tres, pero todos los grafos de prisma más grandes tienen un 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 y los grafos de ruedas (grafos de pirámides ) . Otros grafos poliédricos transitivos en vértices incluyen los grafos arquimedianos .

Si los dos ciclos de un grafo prismático se rompen eliminando una sola arista en la misma posición en ambos ciclos, el resultado es un grafo escalera . Si estas dos aristas eliminadas se reemplazan por dos aristas cruzadas, el resultado es un grafo no planar llamado escalera de Möbius . ^{[ 7 ]}

Un grafo de prisma cruzado es similar, pero empareja aristas cruzadas laterales, alternando hacia adelante y hacia atrás, para prismas de lados pares. El conjunto también incluye grafos regulares , grafos cúbicos transitivos de vértices y grafos bipartitos (también llamados grafos bicúbicos). ^{[ 8 ]} Un grafo de prisma de 4 cruces es igual al grafo cúbico con 8 vértices y 12 aristas. Un grafo de prisma de 6 cruces es también el grafo de Franklin con 12 vértices y 18 aristas. En An Atlas of Graphs, los primeros se enumeran en el conjunto de grafos cúbicos transitivos conectados, indexados como Ct5, Ct12, Ct19, Ct29, Ct42, Ct54 y Ct74 para 4, 6, 8, 10, 12, 14 y 16 lados respectivamente. ^{[ 9 ]}