Bireguláris gráf

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.

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

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

• Ez a szócikk részben vagy egészben a Biregular graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.