Graphe birégulier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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

Les graphes bipartis complets[modifier | modifier le code]

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

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

Le graphe du dodécaèdre rhombique[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) Edward R. Scheinerman et Daniel H. Ullman, Fractional graph theory, New York, John Wiley & Sons Inc.,‎ 1997 (ISBN 0-471-17864-0), p. 137.
  2. a et b (en) Josef Lauri et Raffaele Scapellato, Topics in Graph Automorphisms and Reconstruction, Cambridge University Press,‎ 2003, 20–21 p. (ISBN 9780521529037, 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, Handbook of combinatorial designs, Chapman & Hall/CRC, Boca Raton, FL,‎ 2007, 353–355 p..

Source[modifier | modifier le code]