Scara (teoria graficelor)

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 cu scară inelară

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.

Galerie

Note

  1. ^ Weisstein , Eric W. Ladder Graph  pe site- ul Wolfram MathWorld .
  2. ↑ Hosoya, Harary, 1993 , p. 211-218.
  3. ↑ Noy, Ribó, 2004 , p. 350-363.
  4. ↑ Chen, Gross, Mansour, 2013 , p. 32–57.

Literatură