Регулярный граф

Пусть A есть матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ есть собственный вектор A[1]. Его собственное число будет постоянной степенью графа. Собственные вектора, соответствующие другим собственным числам, ортогональны ${\displaystyle {\textbf {j}}}$, поэтому для собственных векторов ${\displaystyle v=(v_{1},\dots ,v_{n})}$ мы имеем ${\displaystyle \sum _{i=1}^{n}v_{i}=0}$.

Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность[1].

Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с ${\displaystyle J_{ij}=1}$ находится в алгебре смежности графа[2].

Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{n-1}}$. Если G не двудолен:

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(k/\lambda )}}+1}$[3] [4]

где

${\displaystyle \lambda =\max _{i>0}\{\mid \lambda _{i}\mid \}}$.

Регулярный граф можно сгенерировать программой GenReg.[5]

• Случайный регулярный граф  (англ.)
• Сильно регулярный граф
• Граф Мура  (англ.)
• Клетка

• Weisstein, Eric W. Regular Graph (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Strongly Regular Graph (англ.) на сайте Wolfram MathWorld.
• GenReg программа и данные Маркуса Мерингера.
• Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo