| Лестничный график | |
|---|---|
 Лестничный граф L 8 . | |
| Вершины | 2n |
| Края | 3н-2 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 для n> 2 2 для n = 2 1 для n = 1 |
| Характеристики | Единичное расстояние Гамильтониан Планарный Двудольный |
| Обозначение | L n |
| Таблица графиков и параметров | |
В математической области теории графов , на лестничном граф L п является плоской неориентированным граф с 2n вершин и 3n-2 ребром. [1]
Лестничный граф может быть получен как декартово произведение двух графов путей , один из которых имеет только одно ребро: L n , 1 = P n × P 2 . [2] [3]
Свойства [ править ]
По построению лестничный граф L n изоморфен сеточному графу G 2, n и выглядит как лестница с n ступенями. Это гамильтониан с обхватом 4 (если n> 1 ) и хроматическим индексом 3 (если n> 2 ).
Хроматическое число лестничного графа 2 и его хроматический многочлен является .
Хроматическое число лестничного графа 2.
График ступенек [ править ]
Иногда термин «лестница график» используются для п × P 2 лестничной ступеньки графа , который является график объединением п экземпляров пути граф P 2 .
Круговая лестничная диаграмма [ править ]
Круговая лестница график CL п построим путем подключения четыре 2-градусных вершин в прямой форме, либо в декартово произведении цикла длиной n ³ 3 и кромка. [4] В символах CL n = C n × P 2 . Он имеет 2n узлов и 3n ребер. Как и лестничный граф, он связан , планарен и гамильтонов , но двудольный тогда и только тогда, когда n четно.
Круговой лестничный граф - это многогранные графы призм, поэтому их чаще называют призменными графами .
Круговые лестничные диаграммы:
 CL3 |  CL4 |  CL5 |  CL6 |  CL7 |  CL8 |
Лестница Мебиуса [ править ]
Соединение четырех вершин 2 степени крест-накрест создает кубический граф, называемый лестницей Мёбиуса.
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. "Лестничный график" . MathWorld .
- ^ Хосоя, Х. и Харари, Ф. «О совпадающих свойствах трех графов заборов». J. Math. Chem. 12, 211-218, 1993.
- ^ Ной, М. и Рибо, А. «Рекурсивно конструируемые семейства графов». Adv. Прил. Математика. 32, 350-363, 2004.
- ^ Чен, Ичао; Гросс, Джонатан Л .; Мансур, Туфик (сентябрь 2013 г.). «Распределения полного погружения круговых лестниц». Журнал теории графов . 74 (1): 32–57. CiteSeerX 10.1.1.297.2183 . DOI : 10.1002 / jgt.21690 .