RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2008, том 15, выпуск 1, страницы 11–16 (Mi da518)

Эта публикация цитируется в 10 статьях

Высота цикла длины 4 в 1-планарных графах с минимальной степенью 5 без треугольников

О. В. Бородинa, И. Г. Дмитриевb, А. О. Ивановаb

a Институт математики им. С. Л. Соболева СО РАН
b Институт математики и информатики, Якутский государственный университет им. М. К. Аммосова

Аннотация: Граф называется 1-планарным, если его можно изобразить на плоскости так, чтобы каждое ребро скрещивалось не более чем с одним другим ребром. Известно, что в 1-планарном графе есть вершина степени не больше 7, а также либо вершина степени не больше 4, либо цикл длины не больше 4. Доказывается, что 1-планарный граф без треугольников и вершин степени меньше 5 содержит цикл длины 4, состоящий из вершин степени не больше 8. Библ. 8.

УДК: 519.172

Статья поступила: 24.12.2007


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2009, 3:1, 28–31

Реферативные базы данных:


© МИАН, 2024