Demi-hypercube (graphe)

Deux sommets de ${\displaystyle {\frac {1}{2}}Q_{n}}$ sont adjacents dans ${\displaystyle {\frac {1}{2}}Q_{n}}$ si et seulement s'ils se trouvent exactement à une distance de deux dans ${\displaystyle Q_{n}}$. À partir d'un graphe hypercube donné, on peut obtenir deux graphes demi-hypercubes distincts mais isomorphes, suivant le sommet de départ que l'on a choisi.

${\displaystyle {\frac {1}{2}}Q_{4}}$ peut être construit à partir du graphe tesseract ${\displaystyle Q_{4}}$ en enlevant des sommets.	${\displaystyle {\frac {1}{2}}Q_{4}}$ peut aussi être construit à partir du graphe hexaédrique ${\displaystyle Q_{3}}$ en ajoutant des arêtes.

On peut aussi obtenir ${\displaystyle {\frac {1}{2}}Q_{n}}$ à partir de l'hypercube de dimension inférieure ${\displaystyle Q_{n-1}}$ en ajoutant des arêtes entre les sommets à distance deux[1].

Le graphe ${\displaystyle {\frac {1}{2}}Q_{n}}$ est le graphe des arêtes et des sommets d'un objet géométrique, le demi-hypercube de dimension ${\displaystyle n}$.

On peut aussi interpréter ${\displaystyle {\frac {1}{2}}Q_{n}}$ comme le graphe de la relation entre les nombres binaires de longueur ${\displaystyle n}$ comportant un nombre pair de 1 (comme 0, 3, 5, 6, 9, etc.[3]) qui sont à une distance de Hamming égale à deux[4].

Comme c'est la moitié bipartie d'un graphe distance-régulier, le graphe demi-hypercube est lui-même distance-régulier[5].

Comme c'est la moitié bipartie d'un graphe hamiltonien, il est lui-même hamiltonien.

(en) Eric W. Weisstein, « Halved Cube Graph », sur MathWorld

• Moitié bipartie