A matematika, azon belül a gráfelmélet területén egy bireguláris gráf (biregular graph). vagy félreguláris páros gráf (semiregular bipartite graph). olyan páros gráf, melyben adott párosítás egy-egy oldalán az összes csúcs fokszáma megegyezik. Ha az -beli csúcsok fokszáma és a -beli csúcsoké , akkor a gráf -bireguláris.
Példák Bármely teljes páros gráf -bireguláris. A rombododekaéder (3,4)-bireguláris. .
Csúcsszámok Egy -bireguláris gráfban teljesülnie kell a következő egyenlőségnek: . Ez egyszerű kettős leszámlálásból következik: -ban db él végződik, -ben pedig , és az élek mindkét vége 1-1 csúccsal járul hozzá a fenti számokhoz.
Szimmetria Minden reguláris páros gráf bireguláris. Minden éltranzitív gráf (nem tekintve az olyan gráfokat, melyekben izolált csúcsok vannak), ami nem csúcstranzitív, szükségképpen bireguláris.. Sőt, minden éltranzitív gráf reguláris vagy bireguláris.
Konfigurációk A geometriai konfigurációk illeszkedési gráfjai biregulárisak; egy bireguláris gráf pontosan akkor lehet egy absztrakt konfiguráció illeszkedési gráfja, ha girthparamétere legalább hat..
Fordítás
Jegyzetek
Kategória:Gráfelmélet Kategória:Páros gráfok