Biregular graf

I grafteori er en biregulær graf en todelt graf der alle knutepunktene til hver av de to delene av grafen har samme grad . Betegn med og de to delene av en toregulert graf. Hvis graden til toppunktene på er og graden til toppunktene på er , sies grafen å være -bike. $U$ $V$ $U$ $x$ $V$ $y$ $(x, y)$

Eksempler

Komplett tosidige grafer

Enhver komplett tosidig graf ( figur ) er -regulær. ${\ displaystyle K_ {a, b}}$ $(a, b)$

Grafen til den rombiske dodekaederet

Grafen til det rhombiske dodekaederet ( figur ) er -biregular. Faktisk er toppunktene delt inn i to sett: ${\ displaystyle (3,4)}$

settet med hjørner av grad 4; $U$
settet med hjørner av grad 3. $V$

Ingen toppunkt av grad 4 er bundet av en kant til et annet toppunkt av grad 4; ingen toppunkt av grad 3 er knyttet til en kant til et annet toppunkt av grad 3: denne grafen er faktisk tosidig.

Antall hjørner

En biregulær graf av deler og verifiserer likeverd . $U$ $V$ ${\ displaystyle deg (U) \ cdot | U | = deg (V) \ cdot | V |}$

For eksempel, i den rhombiske dodekaederet, har vi 6 hjørner av grad 4 og 8 hjørner av grad 3, det sjekker godt . ${\ displaystyle 6 \ times 4 = 8 \ times 3}$

Vi kan bevise denne likheten ved å telle dobbelt :

antall ender av kantene som ender på er ; $U$ ${\ displaystyle deg (U) \ cdot | U |}$
antall ender av kantene som ender på er ; $V$ ${\ displaystyle deg (V) \ cdot | V |}$
hver kant har en ende og bare en i og en ende og bare en i , så disse to tallene er like. $U$ $V$

Andre egenskaper

En graf - vanlig bipartite er -birégulier. $ikke$ ${\ displaystyle (n, n)}$
En kanttransitiv graf (unntatt grafer med isolerte hjørner) som ikke også er toppunkt-transitiv, er dobbeltregulert.
Spesielt er en topptransitiv graf enten vanlig eller dobbeltregulær.
De Levi grafer av geometriske konfigurasjoner er biregular.
En dobbeltregulert graf er Levi-grafen til en geometrisk (abstrakt) konfigurasjon hvis og bare hvis masken er minst seks.

Merknader og referanser

(in) Edward R. Scheinerman og Daniel H. Ullman , Fractional graph theory , New York, John Wiley & Sons Inc.,1997( ISBN 0-471-17864-0 , Matematiske anmeldelser 1481157 ) , s. 137.
(en) Josef Lauri og Raffaele Scapellato , Emner i grafautorfismer og gjenoppbygging , Cambridge University Press ,2003, 20–21 s. ( ISBN 978-0-521-52903-7 , les online ).
(in) Tamás Réti , " On the relations entre les first and second clues Zagreb " , MATCH Commun. Matte. Beregn. Chem. , vol. 68,2012, s. 169–188 ( les online ).
(in) Harald Gropp , Charles J. Colbourn ( dir. ) And Jeffrey H. Dinitz ( red. ), Handbook of combinatorial designs , Chapman & Hall / CRC, Boca Raton, FL,20072. utg. , 353–355 s. ( ISBN 9781584885061 ) , "VI.7-konfigurasjoner".

Kilde

(fr) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen " Biregular graph " ( se listen over forfattere ) .