Regulá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

Egy gráf reguláris, ha minden csúcsának ugyanannyi szomszédja van, más szóval minden csúcs fokszáma azonos. A közös fokszámot k-val jelölve beszélhetünk k-reguláris gráfról is. A reguláris irányított gráfnak meg kell felelnie annak az erősebb feltételnek is, hogy az egyes csúcsba bemenő élek és kimenő élek száma egyenlő legyen egymással.

Egy erősen reguláris gráf egy olyan reguláris gráf, ahol a szomszédok száma megegyezik minden csúcsnál, de két összekötött csúcs közös szomszédjainak a száma és két nem-összekötött csúcs közös szomszédainak száma is független a két pont választásától.

A kézfogás-lemma szerint minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik.

A Nash-Williams-tétel szerint minden $2k+1$ csúcsú k-reguláris gráfban van Hamilton-kör.

Egzisztencia

Akkor és csak akkor létezik n csúcsú $k$-reguláris gráf, ha , ha $n\ge k+1$ és $nk$ páros. Ebben az esetben egy ilyen reguláris gráf könnyen megkonstruálható megfelelően paraméterezett cirkuláns gráfként.Sablon:Forrás?

Osztályozás

A legfeljebb 2-reguláris gráfok egyszerűen osztályozhatóak.

• A 0-reguláris gráfok nem tartalmaznak éleket, ezek az üres gráfok.
• Az 1-reguláris gráfok egy-egy éllel összekötött csúcspárokat tartalmaznak.
• A 2-reguláris gráfok csúcsidegen körökből állnak.
• A 3-reguláris gráfokat angol nyelvterületen cubic graph-nak nevezik.

• 
  0-reguláris gráf
• 
  1-reguláris gráf
• 
  2-reguláris gráf
• 
  3-reguláris gráf

Algebrai tulajdonságok

Legyen A egy gráf szomszédsági mátrixa.

A gráf akkor és csak akkor reguláris, ha $\mathbf{\text{j}}=(1,\dots ,1)$ sajátvektora A-nak. Ekkor a sajátérték k. A többi sajátértéknek megfelelő sajátvektorok merőlegesek $\mathbf{\text{j}}$-re, tehát az ilyen sajátvektorok koordinátáinak összege nulla.

Egy k-reguláris gráf csak akkor összefüggő, ha k egyszeres sajátértéke. A "csak akkor" meghatározás a Perron–Frobenius-tétel következménye.

Van egy másik kritérium a reguláris és összefüggő gráfokra: egy gráf pontosan akkor reguláris és összefüggő, ha az

$\left[\begin{array}{ccc}1& \cdots & 1\\ ⋮& \ddots & ⋮\\ 1& \cdots & 1\end{array}\right]$

mátrix eleme A szomszédsági algebrájának, azaz előáll A hatványainak lineáris kombinációjaként.

Legyen G k- reguláris gráf, D átmérővel és $k={\lambda }_0>{\lambda }_1\ge \cdots \ge {\lambda }_{n-1}$ sajátértékekkel. Ha G nem páros gráf, akkor

$D\le \frac{\log (n-1)}{\log ({\lambda }_0/{\lambda }_1)}+1.$

Példák

• Minden teljes gráf (erősen) reguláris.
• Minden hiperkockagráf reguláris.
• Az egyenlő nagyságú osztályokkal rendelkező teljes páros gráfok regulárisak.
• Minden gyűrűs kocka 3-reguláris.
• A legkisebb reguláris, de nem erősen reguláris gráf a ciklusgráf és a hatcsúcsú körkörös gráf.

Generálás

Létezik gyors algoritmus az adott fokszámú és csúcsszámú reguláris gráfok izomorfizmus erejéig való felsorolására.

Kapcsolódó szócikkek

• Erősen reguláris gráf
• Cage (gráfelmélet)

További információk

• • Sablon:MathWorld
  • Sablon:MathWorld
  • GenReg software and data by Markus Meringer.
  • Sablon:Citation