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 $U$ et $V$ les deux parties d'un graphe birégulier. Si le degré des sommets de $U$ est $x$ et si le degré des sommets de $V$ est $y$ , le graphe est dit $(x,y)$ -birégulier.

Exemples

Les graphes bipartis complets

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

Le graphe du dodécaèdre rhombique

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

l'ensemble $U$ des sommets de degré 4 ;
l'ensemble $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 $U$ et $V$ vérifie l'égalité $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 $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 $U$ est $deg(U)\cdot |U|$ ;
le nombre d'extrémités des arêtes aboutissant dans $V$ est $deg(V)\cdot |V|$ ;
chaque arête a une extrémité et une seule dans $U$ et une extrémité et une seule dans $V$ , donc ces deux nombres sont égaux.

Autres propriétés

Un graphe $n$ -régulier biparti est $(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

↑ (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.
↑ ^{a et b} (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).
↑ (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).
↑ (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).

Portail des mathématiques

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

[ls03-2] {a et b} (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 ».

[1]

[2]

[3]

[4]