Moitié bipartie

Le demi-cube d'ordre 4, obtenu comme moitié biparti du graphe de l'hypercube d'ordre 4.

En théorie des graphes, la moitié bipartie ou le demi-carré d'un graphe biparti $G=(U,V,E)$ est un graphe $H=(U,F)$ dont l'ensemble des sommets est l'ensemble $U$ (l'un des deux ensembles des sommets de la bipartition) et dans lequel il y a une arête $(u,u^{\prime })$ entre $u$ et $u^{\prime }$ s'ils sont à distance deux dans $G$, en d'autres termes, s'il existe un sommet $v\in V$ tel qu'il existe une arête entre $u$ et $v$ et entre $u^{\prime }$ et $v$ dans le graphe $G$. Dans une notation plus compacte, la moitié bipartie est $H=G^2(U)$, où l'exposant dénote le carré du graphe et l'ensemble entre crochets dénote le sous-graphe induit par $U$.

Par exemple, le demi-carré du graphe biparti complet $K_{n,n}$ est le graphe complet $K_n$K_n et la moité biparti de l'hypercube est le demi-hypercube. Quand $G$ 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 Modèle:Lien 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é

• Modèle:Lien