Moitié bipartie
En théorie des graphes, la moitié bipartie ou le demi-carré d'un graphe biparti  est un graphe  dont l'ensemble des sommets est l'ensemble   (l'un des deux ensembles des sommets de la bipartition) et dans lequel il y a une arête  entre  et  s'ils sont à distance deux dans , en d'autres termes, s'il existe un sommet  tel qu'il existe une arête entre  et  et entre  et  dans le graphe . Dans une notation plus compacte, la moitié bipartie est , où l'exposant dénote le carré du graphe et l'ensemble entre crochets dénote le sous-graphe induit par .

Par exemple, le demi-carré du graphe biparti complet  est le graphe complet Kn et la moité biparti de l'hypercube est le demi-hypercube.
Quand  est un graphe distance-régulier, ses deux moitiés biparties sont des graphes distance-réguliers. 

Par exemple, la moitié bipartie du graphe de Foster est l'un des graphes de la famille finie des graphes distance-réguliers  de degré 6.

Les  « Map graphs » qui sont les graphes d'intersection de régions simplement connexes du plan d'intérieurs disjoints, sont exactement les moitiés biparties de graphes planaires

Article lié

Notes et références 

Opération sur les graphes
Famille de graphes