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

Материал из WikiGrapp
Перейти к:навигация, поиск

Расширенный нечетный граф (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.