В математической области теории графов лестничный граф L n представляет собой плоский неориентированный граф с 2 n вершинами и 3 n – 2 ребрами. [1]
Лестничный граф может быть получен как декартово произведение двух графов путей , один из которых имеет только одно ребро: L n ,1 = P n × P 2 . [2] [3]
По построению лестничный граф L n изоморфен решетчатому графу G 2, n и выглядит как лестница с n перекладинами. Он является гамильтоновым с обхватом 4 (если n>1 ) и хроматическим индексом 3 (если n>2 ).
Хроматическое число лестничного графа равно 2, а его хроматический многочлен равен .
Иногда термин «граф-лестница» используется для графа-ступени n × P 2 , который представляет собой объединение n копий графа-пути P 2 .
Круговой лестничный граф CL n можно построить, соединив четыре вершины 2-степени прямым способом или декартовым произведением цикла длины n ≥ 3 и ребра. [4] В символах CL n = C n × P 2 . Он имеет 2 n узлов и 3 n ребер. Как и лестничный граф, он связный , планарный и гамильтонов , но он двудольный тогда и только тогда, когда n четно.
Круговые лестничные графы — это многогранные графы призм, поэтому их чаще называют призматическими графами .
Круговые лестничные графики:
Соединяя четыре вершины 2-й степени крест-накрест, мы создаем кубический граф, называемый лестницей Мёбиуса.
