Лестничный график - Ladder graph

Лестничный график
Лестничный график L8.
Вершины	2n
Края	3н-2
Хроматическое число	2
Хроматический индекс	3 для п> 2 2 для п = 2 1 для п = 1
Свойства	Единичное расстояние Гамильтониан Планарный Двудольный
Обозначение	Lп
Таблица графиков и параметров

в математический поле теория графов, то лестничный график L_п это планарный неориентированный граф с участием 2n вершины и 3н-2 края.^[1]

Лестничный график можно получить как Декартово произведение из двух графы путей, у одного из которых только одно ребро: L_п,1 = п_п × п₂.^[2][3]

Свойства

По построению лестничный граф L_п изоморфен сетка графика г_2,п и выглядит как лестница с п ступеньки. это Гамильтониан с обхватом 4 (если п> 1) и хроматический индекс 3 (если п> 2).

В хроматическое число лестничного графа равно 2, а его хроматический полином является ${displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}}$.

Лестничные графики L₁, L₂, L₃, L₄ и L₅.

• 

  В хроматическое число лестничного графа равно 2.

Лестничный график

Иногда термин «лестничный график» используется для обозначения п × п₂ лестничный график, который является объединением графов п копии графа путей P₂.

Лестничные диаграммы ступенек LR₁, LR₂, LR₃, LR₄, и LR₅.

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

Основная статья: График призмы

В круговой лестничный график CL_п можно построить, соединив четыре вершины 2-степени в Прямо способом, или декартовым произведением цикла длины n≥3 и край.^[4]В символах CL_п = C_п × п₂. Она имеет 2n узлы и 3n рёбер.Как и лестничный граф, это связанный, планарный и Гамильтониан, но это двудольный если и только если п даже.

Круговой лестничный график - это многогранные графы призм, поэтому их чаще называют призматические графики.

Круговые лестничные диаграммы:

CL3

CL4

CL5

CL6

CL7

CL8

Лестница Мебиуса

Основная статья: Лестница Мебиуса

Соединение четырех вершин 2 степени поперек создает кубический граф называется лестницей Мёбиуса.

Два вида на лестницу Мёбиуса M₁₆ .

использованная литература

1. Вайсштейн, Эрик В. «Лестничный график». MathWorld.
2. Хосоя, Х. и Харари, Ф. «О совпадающих свойствах трех графов заборов». J. Math. Chem. 12, 211-218, 1993.
3. Ной М. и Рибо А. "Рекурсивно конструируемые семейства графов". Adv. Appl. Математика. 32, 350-363, 2004.
4. Чен, Ичао; Гросс, Джонатан Л .; Мансур, Туфик (сентябрь 2013 г.). «Распределения полного погружения круговых лестниц». Журнал теории графов. 74 (1): 32–57. CiteSeerX  10.1.1.297.2183. Дои:10.1002 / jgt.21690.