Reguláris gráf

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.

Osztályozás

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

• A 0-reguláris gráfok nem tartalmaznak éleket.
• 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.

• 

  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 $G=(V, E)$ gráf szomszédsági mátrixa.

1. G pontosan akkor reguláris, ha az $\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}$ vektor sajátvektora $A$-nak.
2. Egy k-reguláris gráf pontosan akkor összefüggő, ha k egyszeres sajátértéke.
3. Egy gráf pontosan akkor reguláris és összefüggő, ha az $\begin{bmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{bmatrix}$ mátrix eleme az $A$ mátrix szomszédsági algebrájának, azaz előáll $A$ hatványainak lineáris kombinációjaként (A. J. Hoffmann, 1963).

Példák

1. Minden teljes gráf reguláris.
2. Minden hiperkocka gráf reguláris.
3. Az egyenlő nagyságú osztályokkal rendelkező teljes páros gráfok regulárisak.
4. Minden gyűrűs kocka 3-reguláris.