Драбина (теорія графів)
В теорії графів драбина Ln — планарний неорієнтований граф з 2n вершинами і n+2(n-1) ребрами .
| Ladder graph | |
|---|---|
 Граф драбина L8. | |
| Вершин | 2n |
| Ребер | 3n-2 |
| Хроматичне число | 2 |
| Хроматичний індекс |
3 для n>2 2 для n=2 1 для n=1 |
| Властивості |
одиничних відстаней гамільтонів планарний двочастковий |
| Позначення | Ln |
Драбину можна отримати прямим добутком двох шляхів, один з яких має тільки одне ребро — Ln,1 = Pn × P1 [1][2]. Якщо додати ще два ребра, що перетинаються і з'єднують чотири вершини драбини зі степенем два, одержимо кубічний граф — драбину Мебіуса.
З побудови, драбина Ln ізоморфна решітці G2,n і виглядає як драбина з n щаблями. Граф є гамільтоновим з охопленням 4 (якщо n>1) і хроматичним індексом 3 (якщо n>2).
Хроматичне число драбини дорівнює 2, а її хроматичний многочлен дорівнює .
Кільцевий драбинний граф
Кільцевий драбинний граф CLn — це прямий добуток циклу довжини n≥3 і ребра[3]. В символьному вигляді CLn = Cn × P1. Граф має 2n вершин і 3n ребер. Подібно до драбини граф є зв'язним, планарним і гамільтоновим, але граф є двочастковим тоді й лише тоді, коли n парне.
Кільцевий драбинний граф — це багатогранний граф призм, тому його частіше називають графом призми.
Кільцеві драбинні графи:
 CL3 |
 CL4 |
 CL5 |
 CL6 |
 CL7 |
 CL8 |
Драбина Мебіуса
З'єднавши чотири вершини степеня 2 «навхрест», отримаємо кубічний граф, який називають драбиною Мебіуса.
Примітки
- Hosoya, Harary, 1993, с. 211-218.
- Noy, Ribó, 2004, с. 350-363.
- Chen, Gross, Mansour, 2013, с. 32–57.
Література
- H. Hosoya, F. Harary. On the Matching Properties of Three Fence Graphs // J. Math. Chem.. — 1993. — Вип. 12 (7 лютого). — С. 211-218.
- M. Noy, A. Ribó. Recursively Constructible Families of Graphs // Adv. Appl. Math. — 2004. — Вип. 32 (7 лютого). — С. 350-363.
- Yichao Chen, Jonathan L. Gross, Toufik Mansour. Total Embedding Distributions of Circular Ladders // Journal of Graph Theory. — 2013. — Т. 74, вип. 1 (1 вересня). — С. 32–57. — DOI:.