Graphe prismatique

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 ${\displaystyle Y_{n}}$. Les graphes sont nommés d'après le solide associé :

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

Y3 = GP(3,1)

Y4 = Q3 = GP(4,1)

Y5 = GP(5,1)

Y6 = GP(6,1)

Y7 = GP(7,1)

Y8 = 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.

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[1].

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 ${\displaystyle 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 ${\displaystyle \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[1].

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

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[2].

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 ${\displaystyle O(2^{n/2})}$ 1-factorisations, et les graphes prismatiques ont ${\displaystyle \Omega (2^{n/2})}$ 1-factorisations[3].

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

${\displaystyle {\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[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].

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].

• (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).

• Portail des mathématiques
• Portail de l'informatique théorique