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

Лестницу можно получить как прямое произведение двух путей , один из которых имеет только одно ребро — L _n = P _n × P ₁ . Если добавить ещё два пересекающихся ребра, соединяющих четыре вершины лестницы со степенью два, получим кубический граф — лестницу Мёбиуса .

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

Хроматическое число лестницы равно 2, а её хроматический многочлен равен ${\displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}}$ .

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

Кольцевой лестничный граф CL _n — это прямое произведение цикла длины n≥3 и ребра . В символьном виде CL _n = C _n × P ₁ . Граф имеет 2n вершин и 3n рёбер. Подобно лестницам граф является связным , планарным и гамильтоновым , но граф является двудольным тогда и только и тогда, когда n чётно.

Галерея

• 
  Хроматическое число лестницы равно 2.

Примечания

Литература

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