Graphe octaédrique

Il existe cinq graphes correspondant aux squelettes des cinq solides de Platon. Le graphe octaédrique est celui correspondant à l'octaèdre régulier. Les quatre autres sont le graphe tétraédrique, le graphe hexaédrique, le graphe dodécaédrique et le graphe icosaédrique.

Le graphe octaédrique est également isomorphe au graphe circulant ${\displaystyle Ci_{6}(1,2)}$, le graphe à 6 sommets où, pour tout ${\displaystyle i}$, le ${\displaystyle i}$-ème sommet est adjacent aux sommets ${\displaystyle i+1}$ et ${\displaystyle i+2}$ modulo 6.

Le diamètre du graphe octaédrique, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 4-sommet-connexe et d'un graphe 4-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 4 sommets ou de 4 arêtes.

Le graphe octaédrique est planaire. Il a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête n'en croise une autre. À partir de cette représentation, il est possible de définir son graphe dual. C'est le graphe dont les sommets correspondent aux faces du graphe octaédrique et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. Ce dual est isomorphe au graphe hexaédrique.

• 
  3-coloration des sommets.
• 
  4-coloration des arêtes.

Le nombre chromatique du graphe octaédrique est 3. C'est-à-dire qu'il est possible de colorer ses sommets avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du graphe octaédrique est 4. Il existe donc une 4-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Il est possible de compter les colorations distinctes des sommets d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme admet pour racines tous les entiers positifs ou nuls strictement inférieurs à 3 et est de degrés 6. Il est égal à : ${\displaystyle (x-2)(x-1)x(x^{3}-9x^{2}+29x-32)}$.

• 
  Premier type de cycle hamiltonien.
• 
  Le même vu dans dans l'octaèdre ; angles de 60° entre deux arêtes successives.
• 
  Deuxième type de cycle hamiltonien.
• 
  Dans l'octaèdre ; succession des angles en degrés : 60,60,90,60,60,90.

Le graphe octaédrique possède 240 chemins hamiltoniens (passant une fois et une seule par chacun des six sommets), et 32 cycles hamiltoniens^[1]. Représenté sur l'octaèdre régulier, il ne possède plus que 2 cycles hamiltoniens à isométrie près.

Cela signifie qu'il existe exactement deux façons de "peler" successivement les six faces d'un cube (deux faces successives étant séparées par une arête) en un chemin fermé^[2].

Le groupe d'automorphismes du graphe octaédrique est un groupe d'ordre 48.

Le polynôme caractéristique de la matrice d'adjacence du graphe octaédrique est : ${\displaystyle (x-4)x^{3}(x+2)^{2}}$. Il n'admet que des racines entières. Le graphe octaédrique est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

• Théorie des graphes

• (en) Eric W. Weisstein, Octahedral Graph (MathWorld)

• Portail des mathématiques