Graphe prismatique
# Graphe prismatique

En théorie des graphes, un graphe prismatique ou graphe de prisme est un graphe qui correspond au squelette d'un prisme.

## Exemples

Les graphes prismatiques sont des exemples de graphes de Petersen généralisés, avec des paramètres GP( n ,1). Ils sont aussi notés $Y_{n}$. Les graphes sont nommés d'après le solide associé :

* $Y_{3}$ : Graphe prismatique triangulaire – 6 sommets, 9 arêtes
* $Y_{4}$ : Graphe cubique – 8 sommets, 12 arêtes
* $Y_{5}$ : Graphe prismatique pentagonal – 10 sommets, 15 arêtes
* $Y_{6}$ : Graphe prismatique hexagonal – 12 sommets, 18 arêtes
* $Y_{7}$ : Graphe prismatique heptagonal – 14 sommets, 21 arêtes
* $Y_{8}$ : Graphe prismatique octogonal – 16 sommets, 24 arêtes

    $Y_3$ = GP(3,1) $Y_4$ = $Q_3$ = GP(4,1) $Y_5$ = GP(5,1) $Y_6$ = GP(6,1) $Y_7$ = GP(7,1) $Y_8$ = GP(8,1)

Les polygones étoilés, forment géométriquement aussi les faces d'une suite de polyèdres prismatiques (auto-sécants et non convexes) ; les graphes de ces prismes étoilés sont isomorphes aux graphes prismatiques et ne forment pas une suite séparée de graphes.

## Construction

Les graphes prismatiques sont des exemples de graphes de Petersen généralisés, avec des paramètres GP( n ,1). Ils peuvent également être construits comme le produit cartésien d'un graphe cycle avec une seule arête.

Comme de nombreux graphes sommet-transitifs, les graphes prismatiques peuvent également être construits comme des graphes de Cayley. Le groupe diédral d'ordre n est le groupe de symétries d'un polygone régulier de taille n dans le plan ; le groupe agit sur le polygone par rotations et réflexions. Il peut être engendré par deux éléments, une rotation d'un angle de $2\pi /n$ et une seule réflexion, et son graphe de Cayley avec cet ensemble de générateurs est le graphe prismatique. De manière abstraite, le groupe a la présentation $\langle r,f\mid r^{n},f^{2},(rf)^{2}\rangle$ (où r est une rotation et f est une réflexion ou un retournement) et le graphe de Cayley a r et f (ou r, r $^{−1}$ et f ) comme générateurs.

Les graphes de prismes polygonaux avec des valeurs impaires de n peuvent être construits comme des graphes circulants $C_{2n}^{2,n}$. Cette construction ne s'applique pas les valeurs paires de n.

Le graphe d'un prisme polygonal possède 2 n sommets et 3 n arêtes. Ce sont des graphes réguliers cubiques. Puisque le prisme a des symétries envoyant chaque sommet sur tout autre sommet, les graphes prismatiques sont des graphes sommet-transitifs. En tant que graphes polyédriques, ce sont également de graphes planaires 3-sommets-connexes. Chaque graphe prismatique possède un cycle hamiltonien.

Parmi tous les graphes cubiques biconnexes, les graphes prismatiques ont, à un facteur constant près, le plus grand nombre possible de 1-factorisations. Une 1-factorisation est une partition de l'ensemble des arêtes du graphe en trois couplages parfaits ou, de manière équivalente, une coloration des arêtes du graphe avec trois couleurs. Chaque graphe cubique à n sommets biconnexe possède $O(2^{n/2})$ 1-factorisations, et les graphes prismatiques ont $\Omega (2^{n/2})$ 1-factorisations.

Le nombre d'arbres couvrants d'un graphe de prisme de taille n est donné par la formule :

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

Pour n = 3, 4, 5, ... ces nombres sont

    75, 384, 1805, 8100, 35287, 150528, ...( suite A006235 de l'OEIS).

Les graphes prismatiques de polygones de taille n sont des cubes partiels. Ils forment l'une des rares familles infinies connues de graphes cubiques partiels et, à l'exception de quatre exemples sporadiques, ce sont les seuls cubes partiels cubiques sommet-transitifs.

Le prisme pentagonal est l'un des mineur exclus pour les graphes de largeur arborescente égale à 3. Le prisme triangulaire et le graphe cubique ont une largeur d'arbre exactement égale à 3, et tous les graphes prismatiques plus grands ont une largeur d'arbre 4.

## Graphes associés

D'autres suites infinies de graphes polyédriques formés de manière similaire à partir de polyèdres avec une base de polygones réguliers sont les graphes graphes d'antiprismes, les graphes roues (graphes de pyramides). D'autres graphes polyédriques sommet-transitifs incluent les graphes d'Archimède .

Si les deux cycles d'un graphe prismatique sont ouverts par la suppression d'une seule arête à la même position dans les deux cycles, le résultat est un graphe en échelle . Si ces deux arêtes supprimées sont remplacées par deux arêtes croisées, le résultat est un graphe non planaire appelé échelle de Möbius.

