Graphe birégulier

Dans la théorie des graphes, un graphe birégulier^[1] est un graphe biparti dans lequel tous les sommets de chacune des deux parties du graphe ont le même degré. Notons ${\displaystyle U}$ et ${\displaystyle V}$ les deux parties d'un graphe birégulier. Si le degré des sommets de ${\displaystyle U}$ est ${\displaystyle x}$ et si le degré des sommets de ${\displaystyle V}$ est ${\displaystyle y}$, le graphe est dit ${\displaystyle (x,y)}$-birégulier.

Exemples

Le graphe biparti complet ${\displaystyle K_{3,2}}$ est ${\displaystyle (3,2)}$-birégulier.

Les graphes bipartis complets

Tout graphe biparti complet ${\displaystyle K_{a,b}}$ (figure) est ${\displaystyle (a,b)}$-birégulier^[2].

Le graphe du dodécaèdre rhombique est birégulier.

Le graphe du dodécaèdre rhombique

Le graphe du dodécaèdre rhombique (figure) est ${\displaystyle (3,4)}$-birégulier^[3]. En effet, ses sommets se répartissent en deux ensembles :

• l'ensemble ${\displaystyle U}$ des sommets de degré 4 ;
• l'ensemble ${\displaystyle V}$ des sommets de degré 3.

Aucun sommet de degré 4 n'est lié par une arête à un autre sommet de degré 4 ; aucun sommet de degré 3 n'est lié par une arête à un autre sommet de degré 3 : ce graphe est bien biparti.

Nombre de sommets

Un graphe birégulier de parties ${\displaystyle U}$ et ${\displaystyle V}$ vérifie l'égalité ${\displaystyle deg(U)\cdot |U|=deg(V)\cdot |V|}$.

Par exemple, dans le dodécaèdre rhombique, on a 6 sommets de degré 4 et 8 sommets de degré 3, il vérifie bien ${\displaystyle 6\times 4=8\times 3}$.

On peut prouver cette égalité par double dénombrement :

• le nombre d'extrémités des arêtes aboutissant dans ${\displaystyle U}$ est ${\displaystyle deg(U)\cdot |U|}$ ;
• le nombre d'extrémités des arêtes aboutissant dans ${\displaystyle V}$ est ${\displaystyle deg(V)\cdot |V|}$ ;
• chaque arête a une extrémité et une seule dans ${\displaystyle U}$ et une extrémité et une seule dans ${\displaystyle V}$, donc ces deux nombres sont égaux.

Autres propriétés

• Un graphe ${\displaystyle n}$-régulier biparti est ${\displaystyle (n,n)}$-birégulier.
• Un graphe arête-transitif (en excluant les graphes avec des sommets isolés) qui n'est pas aussi sommet-transitif est birégulier^[2].
• En particulier, un graphe sommet-transitif est soit régulier, soit birégulier.
• Les graphes de Levi de configurations géométriques sont biréguliers.
• Un graphe birégulier est le graphe de Levi d'une configuration géométrique (abstraite) si et seulement si sa maille vaut au moins six^[4].

Notes et références

1. (en) Edward R. Scheinerman et Daniel H. Ullman, Fractional graph theory, New York, John Wiley & Sons Inc., 1997 (ISBN 0-471-17864-0, MR 1481157), p. 137.
2. (en) Josef Lauri et Raffaele Scapellato, Topics in Graph Automorphisms and Reconstruction, Cambridge University Press, 2003, 20–21 p. (ISBN 978-0-521-52903-7, lire en ligne).
3. (en) Tamás Réti, « On the relationships between the first and second Zagreb indices », MATCH Commun. Math. Comput. Chem., vol. 68,‎ 2012, p. 169–188 (lire en ligne).
4. (en) Harald Gropp, Charles J. Colbourn (dir.) et Jeffrey H. Dinitz (dir.), Handbook of combinatorial designs, Chapman & Hall/CRC, Boca Raton, FL, 2007, Seconde éd., 353–355 p. (ISBN 9781584885061), « VI.7 Configurations ».

Source

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