Moitié bipartie

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')$ entre $u$ et $u'$ 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'$ 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$.

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

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 localement linéaires (en) 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é

• Couverture biparti double (en)

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bipartite half » (voir la liste des auteurs).