Нечетный граф

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

Нечетный граф (Odd graph) — граф \,O_{k} = (V(O_{k}), E(O_{k})), k \geq 2, у которого V(O_{k}) = \{A \, | \, A \subseteq \{1,2, \ldots, 2k-1\}, \;
|A| = k-1\}, E(O_{k}) = \{(A,A') \, | \, A \cap A' =
\emptyset\}. Для \,k=2 и \,k=3 наименьшие нечетные графы — это треугольник O_{2} \cong K_{3}и граф Петерсена O_{3}
\cong P_{10}. Для \,k = 4 обхват нечетного графа \,g(O_{k}) = 6.

Литература

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