Лестница (теория графов)

В теории графов лестница Ln — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами [1].

Граф «Лестница»
Вершин 2n
Рёбер n+2(n-1)
Хроматическое число 2
Хроматический индекс 3 для n>2
2 для n=2
1 для n=1
Свойства граф единичных расстояний
гамильтонов
планарный
двудольный
Обозначение Ln
 Медиафайлы на Викискладе

Лестницу можно получить как прямое произведение двух путей, один из которых имеет только одно ребро — Ln = Pn × P1 [2][3]. Если добавить ещё два пересекающихся ребра, соединяющих четыре вершины лестницы со степенью два, получим кубический граф — лестницу Мёбиуса.

По построению, лестница Ln изоморфна решётке G2,n и выглядит как лестница с n перекладинами. Граф является гамильтоновым с обхватом 4 (если n>1) и хроматическим индексом 3 (если n>2).

Хроматическое число лестницы равно 2, а её хроматический многочлен равен .

Кольцевой лестничный граф

Кольцевой лестничный граф CLn — это прямое произведение цикла длины n≥3 и ребра [4]. В символьном виде CLn = Cn × P1. Граф имеет 2n вершин и 3n рёбер. Подобно лестницам граф является связным, планарным и гамильтоновым, но граф является двудольным тогда и только и тогда, когда n чётно.

Галерея
Лестница L1, L2, L3, L4 и L5.

Примечания
  1. Weisstein, Eric W. Ladder Graph (англ.) на сайте Wolfram MathWorld.
  2. Hosoya, Harary, 1993, с. 211-218.
  3. Noy, Ribó, 2004, с. 350-363.
  4. Chen, Gross, Mansour, 2013, с. 32–57.

Литература
  • H. Hosoya, F. Harary. On the Matching Properties of Three Fence Graphs // J. Math. Chem.. — 1993. — Вып. 12. — С. 211-218.
  • M. Noy, A. Ribó. Recursively Constructible Families of Graphs // Adv. Appl. Math. — 2004. — Вып. 32. — С. 350-363.
  • Yichao Chen, Jonathan L. Gross, Toufik Mansour. Total Embedding Distributions of Circular Ladders // Journal of Graph Theory. — 2013. — Т. 74, вып. 1. — С. 32–57. — doi:10.1002/jgt.21690.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.