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

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

$V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\}$

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

$E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1$ или $|A \triangle A'| = 2k-2\},$

где $\triangle$ — симметрическая разность составляющих подмножеств.

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

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

Литература

• Mulder H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.