Earl „Scara” | |
---|---|
Vârfurile | 2n |
coaste | n+2(n-1) |
Număr cromatic | 2 |
Indicele cromatic |
3 pentru n>2 2 pentru n=2 1 pentru n=1 |
Proprietăți |
Graficul de distanță al unității hamiltoniene planar bipartit |
Desemnare | L n |
Fișiere media la Wikimedia Commons |
În teoria grafurilor, o scară L n este un graf plan nedirecționat cu 2n vârfuri și n+2(n-1) muchii [1] .
Scara poate fi obținută ca produs direct a două căi , dintre care unul are o singură muchie - L n = P n × P 1 [2] [3] . Dacă mai adăugăm două muchii care se intersectează care conectează cele patru vârfuri ale unei scări cu gradul doi, obținem un grafic cubic - scara Möbius .
Prin construcție, scara L n este izomorfă cu rețeaua G 2, n și arată ca o scară cu n trepte. Graficul este hamiltonian cu circumferința 4 (dacă n>1 ) și indicele cromatic 3 (dacă n>2 ).
Numărul cromatic al scării este 2, iar polinomul său cromatic este .
Graficul scării inelare CL n este produsul direct al unui ciclu de lungime n≥3 și o muchie [4] . În formă simbolică CL n = C n × P 1 . Graficul are 2n vârfuri și 3n muchii. La fel ca scări, un graf este conexat , planar și hamiltonian , dar un graf este bipartit dacă și numai dacă n este par.
Numărul cromatic al scărilor este 2.