Moitié bipartie

En théorie des graphes, la moitié bipartie ou le demi-carré d'un graphe biparti ${\displaystyle G=(U,V,E)}$ est un graphe ${\displaystyle H=(U,F)}$ dont l'ensemble des sommets est l'ensemble ${\displaystyle U}$ (l'un des deux ensembles des sommets de la bipartition) et dans lequel il y a une arête ${\displaystyle (u,u')}$ entre ${\displaystyle u}$ et ${\displaystyle u'}$ s'ils sont à distance deux dans ${\displaystyle G}$^[1], en d'autres termes, s'il existe un sommet ${\displaystyle v\in V}$ tel qu'il existe une arête entre ${\displaystyle u}$ et ${\displaystyle v}$ et entre ${\displaystyle u'}$ et ${\displaystyle v}$ dans le graphe ${\displaystyle G}$. Dans une notation plus compacte, la moitié bipartie est ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle K_{n,n}}$ est le graphe complet ${\displaystyle K_{n}}$K_n et la moité biparti de l'hypercube est le demi-hypercube. Quand ${\displaystyle G}$ est un graphe distance-régulier, ses deux moitiés biparties sont des graphes distance-réguliers^[2].

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^[3].

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^[4]

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).

1. Robin J. Wilson, Topics in Algebraic Graph Theory, vol. 102, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications », 2004 (ISBN 9780521801973, lire en ligne), p. 188.
2. Laura Chihara et Dennis Stanton, « Association schemes and quadratic transformations for orthogonal polynomials », Graphs and Combinatorics, vol. 2, n^o 2,‎ 1986, p. 101–112 (DOI 10.1007/BF01788084, MR 932118).
3. Akira Hiraki, Kazumasa Nomura et Hiroshi Suzuki, « Distance-regular graphs of valency 6 and ${\displaystyle a_{1}=1}$ », Journal of Algebraic Combinatorics, vol. 11, n^o 2,‎ 2000, p. 101–134 (DOI 10.1023/A:1008776031839 , MR 1761910)
4. Zhi-Zhong Chen, Michelangelo Grigni et Christos H. Papadimitriou, « Map graphs », Journal of the ACM, vol. 49, n^o 2,‎ 2002, p. 127–138 (DOI 10.1145/506147.506148, MR 2147819, arXiv cs/9910013).

• Portail des mathématiques