Familles de graphes définies par leurs automorphismes
distance-transitif distance-régulier fortement régulier
symétrique (arc-transitif) t-transitif, (t ≥ 2) symétrique gauche (en)
(si connexe)
sommet-transitif et arête-transitif
régulier et arête-transitif arête-transitif
sommet-transitif régulier (si biparti)
birégulier
graphe de Cayley zéro-symétrique (en) asymétrique

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

ExemplesModifier

 
Le graphe biparti complet   est  -birégulier.

Les graphes bipartis completsModifier

Tout graphe biparti complet   (figure) est  -birégulier[2].

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

Le graphe du dodécaèdre rhombiqueModifier

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

  • l'ensemble   des sommets de degré 4 ;
  • l'ensemble   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 sommetsModifier

Un graphe birégulier de parties   et   vérifie l'égalité  .

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  .

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

  • le nombre d'extrémités des arêtes aboutissant dans   est   ;
  • le nombre d'extrémités des arêtes aboutissant dans   est   ;
  • chaque arête a une extrémité et une seule dans   et une extrémité et une seule dans  , donc ces deux nombres sont égaux.

Autres propriétésModifier

Notes et référencesModifier

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

SourceModifier