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

Расширенный нечетный граф (Extended odd graph) — граф [math]\displaystyle{ E_{k},\,k \geq 2, }[/math] с множеством вершин

[math]\displaystyle{ V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\} }[/math]

и множеством ребер

[math]\displaystyle{ E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1 }[/math] или [math]\displaystyle{ |A \triangle A'| = 2k-2\}, }[/math]

где [math]\displaystyle{ \triangle }[/math] — симметрическая разность составляющих подмножеств.

Для [math]\displaystyle{ \,k =2 }[/math] или [math]\displaystyle{ \,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 H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.