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 .
Les graphes sont nommés d'après le solide associé :
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.
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 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 (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[1].
Les graphes de prismes polygonaux avec des valeurs impaires de n peuvent être construits comme des graphes circulants. Cette construction ne s'applique pas les valeurs paires de n[1].
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 1-factorisations, et les graphes prismatiques ont 1-factorisations[3].
Le nombre d'arbres couvrants d'un graphe de prisme de taille n est donné par la formule[4] :
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[5].
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[6].
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[7].
Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Prism graph » (voir la liste des auteurs).
↑A. A. Jagers, « A note on the number of spanning trees in a prism graph », International Journal of Computer Mathematics, vol. 24, no 2, , p. 151–154 (DOI10.1080/00207168808803639).