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

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

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 ${\displaystyle 2k+1}$ csúcsú k-reguláris gráfban van Hamilton-kör.

Akkor és csak akkor létezik n csúcsú ${\displaystyle k}$-reguláris gráf, ha , ha ${\displaystyle n\geq k+1}$ és ${\displaystyle 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.

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

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

A gráf akkor és csak akkor reguláris, ha ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ sajátvektora A-nak.^[2] Ekkor a sajátérték k. A többi sajátértéknek megfelelő sajátvektorok merőlegesek ${\displaystyle {\textbf {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.^[2]

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

${\displaystyle {\begin{bmatrix}1&\cdots &1\\\vdots &\ddots &\vdots \\1&\cdots &1\end{bmatrix}}}$

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

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

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$

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

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

Ez a szócikk részben vagy egészben a Regular 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.

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

• • Weisstein, Eric W.: Regular Graph (angol nyelven). Wolfram MathWorld
  • Weisstein, Eric W.: Strongly Regular Graph (angol nyelven). Wolfram MathWorld
  • GenReg software and data by Markus Meringer.
  • Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo