Стълба (теория на графите)
Ърл "Стълба"ВърховеРеброХроматично числоХроматичен индексСвойстваОбозначение |
| 2n |
| n+2(n-1) |
| 2 |
| 3 заn>22 заn=21 заn=1 |
| графика на единично разстояние хамилтонова равнинна двустранна |
| Ln |
Стълбата може да се получи като директно произведение на два пътя, единият от които има само един ръб —Ln,1 =Pn×P1 [2] [3] . Ако добавим още две пресичащи се ребра, свързващи четирите върха на стълба със степен две, получаваме кубична графа - стълбата на Мьобиус.
По конструкция стълбата Lnе изоморфна на решеткатаG2,nи изглежда като стълба сnстъпала. Графиката е Хамилтонова с обиколка 4 (акоn>1) и хроматичен индекс 3 (акоn>2).
Хроматичното число на стълбата е 2 и нейният хроматичен полином е ( x − 1 ) x ( x 2 − 3 x + 3 ) ( n − 1 ) -3x+3)^> .
Съдържание
Кръгла стълбовидна графаCLnе директно произведение на цикъл с дължинаn≥3и ребро [4] . СимволичноCLn=Cn×P1. Графът има2nвърха и3nребра. Подобно на стълбите, графиката е свързана, равнинна и хамилтонова, но графиката е двустранна тогава и само акоnе четен.