Bireguláris gráf

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

A matematika, azon belül a gráfelmélet területén egy bireguláris gráf (biregular graph)^[1] vagy félreguláris páros gráf (semiregular bipartite graph)^[2] olyan ${\displaystyle 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 ${\displaystyle U}$-beli csúcsok fokszáma ${\displaystyle x}$ és a ${\displaystyle V}$-beli csúcsoké ${\displaystyle y}$, akkor a gráf ${\displaystyle (x,y)}$-bireguláris.

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

Egy ${\displaystyle G=(U,V,E)}$ ${\displaystyle (x,y)}$-bireguláris gráfban teljesülnie kell a következő egyenlőségnek: ${\displaystyle x|U|=y|V|}$. Ez egyszerű kettős leszámlálásból következik: ${\displaystyle U}$-ban ${\displaystyle x|U|}$ db él végződik, ${\displaystyle V}$-ben pedig ${\displaystyle y|V|}$, és az élek mindkét vége 1-1 csúccsal járul hozzá a fenti számokhoz.

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.^[3] Sőt, minden éltranzitív gráf reguláris vagy bireguláris.

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.^[5]

• 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.