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

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

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

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

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

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

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