Расширенный нечетный граф

Расширенный нечетный граф (Extended odd graph) - граф [math]\displaystyle{ E_{k} }[/math] [math]\displaystyle{ k \geq 2 }[/math], с множеством вершин [math]\displaystyle{ V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\} }[/math] \noindent и множеством ребер [math]\displaystyle{ E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1 \mbox{ или } |A \triangle A'| = 2k-2\}, }[/math] \noindent где [math]\displaystyle{ \triangle }[/math] --- симметрическая разность составляющих подмножеств.

Для [math]\displaystyle{ k =2\mbox{ или } 3 }[/math] наименьшие расширенные нечетные графы --- это полный [math]\displaystyle{ K_{4} \cong E_{2} }[/math]и граф Гринвуда---Глисона [math]\displaystyle{ E_{3} }[/math]

Граф [math]\displaystyle{ E_{k} }[/math]является дистанционно-транзитивным. Наименьший нечетный цикл в [math]\displaystyle{ E_{k} }[/math]имеет длину [math]\displaystyle{ 2k-1 }[/math].

Литература

[Mulder]