Bireguláris gráf

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	$\mathit{\to }$	távolságreguláris	$\mathit{\leftarrow }$	erősen reguláris
$\mathit{\downarrow }$
szimmetrikus	$\mathit{\leftarrow }$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
$\mathit{\downarrow }$
(ha összefüggő) csúcs- és éltranzitív	$\mathit{\to }$	éltranzitív és reguláris	$\mathit{\to }$	éltranzitív
$\mathit{\downarrow }$		$\mathit{\downarrow }$		$\mathit{\downarrow }$
csúcstranzitív	$\mathit{\to }$	reguláris	$\mathit{\to }$	(ha páros) bireguláris
$\mathit{\uparrow }$
Cayley-gráf	$\mathit{\leftarrow }$	zérószimmetrikus		aszimmetrikus

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 $G=(U,V,E)$ páros gráf, melyben adott párosítás egy-egy oldalán az összes csúcs fokszáma megegyezik. Ha az $U$-beli csúcsok fokszáma $x$ és a $V$-beli csúcsoké $y$, akkor a gráf $(x,y)$-bireguláris.

A rombododekaéder élváza bireguláris.

Példák

Bármely $K_{a,b}$ teljes páros gráf $(b,a)$-bireguláris. A rombododekaéder (3,4)-bireguláris.

Csúcsszámok

Egy $G=(U,V,E)$ $(x,y)$-bireguláris gráfban teljesülnie kell a következő egyenlőségnek: $x|U|=y|V|$. Ez egyszerű kettős leszámlálásból következik: $U$-ban $x|U|$ db él végződik, $V$-ben pedig $y|V|$, é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

• Sablon:Fordítás