Драбина (теорія графів)

Драбину можна отримати прямим добутком двох шляхів, один з яких має тільки одне ребро — L_n,1 = 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 парне.