WikiSort.ru - Не сортированное

Нерешённые проблемы математики: Содержит ли кубический граф простой цикл длиной, равной степени двойки?

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

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

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

Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество ${\displaystyle S}$ длин, с ${\displaystyle |S|=\mathrm {O} (n^{0,99})}$ , такое, что любой граф со средней степенью десять или более содержит цикл с длиной из ${\displaystyle S}$ ^[1]. Известно также, что гипотеза верна для планарных графов без клешней^[2] и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин^[3].

Примечания

Литература

• 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.

Ссылки

• Exoo, Geoffrey. Graphs Without Cycles of Specified Lengths (неопр.). Архивировано 17 марта 2013 года.
• West, Douglas B. Erdős Gyárfás Conjecture on 2-power Cycle Lengths (неопр.). Open Problems - Graph Theory and Combinatorics. Архивировано 17 марта 2013 года.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.