Гипотеза Эрдёша — Дьярфаша

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Question mark2.svg
Нерешённые проблемы математики: Содержит ли кубический граф простой цикл длиной, равной степени двойки?
Граф Маркстрёма с 24 вершинами, являющийся кубическим планарным графом без циклов длины 4 и 8, найденный в процессе компьютерного поиска контрпримера гипотезе Эрдёша — Дьярфаша. Он имеет, однако, циклы длиной 16.

Гипотеза Эрдёша — Дьярфаша  — нерешённая проблема в теории графов, недоказанное утверждение о том, что любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.

Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Андрашем Дьярфашем (англ.).

Компьютерный поиск, осуществлённый Гордоном Ройлом (англ.) и Класом Маркстрёмом (Klas Markström) показал, что любой контрпример должен иметь минимум 17 вершин и любой кубический контрпример должен иметь минимум 30 вершин. Поиск Маркстрёма дал четыре графа с 24 вершинами, имеющих циклы степени двойки только с 16 вершинами, при этом один из этих графов является планарным.

Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество длин, с , такое, что любой граф со средней степенью десять или более содержит цикл с длиной из [1]. Известно также, что гипотеза верна для планарных графов без клешней[2] и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин[3].

Примечания[править | править вики-текст]

  1. Jacques Verstraëte Unavoidable cycle lengths in graphs // Journal of Graph Theory. — 2005. — Т. 49, вып. 2. — С. 151–167. — DOI:10.1002/jgt.20072.
  2. Dale Daniel, Stephen E. Shauger. Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 2001. — С. 129–139.
  3. Stephen E. Shauger. Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 1998. — С. 61–65.

Литература[править | править вики-текст]

  • Extremal graphs for some problems on cycles in graphs // Congr. Numerantium. — 2004. — Т. 171. — С. 179–192.
  • Benny Sudakov, Jacques Verstraëte Cycle lengths in sparse graphs // Combinatorica. — 2008. — Т. 28. — С. 357–372. — DOI:10.1007/s00493-008-2300-6. — arXiv:0707.2117.

Ссылки[править | править вики-текст]