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