Létra (gráfelmélet)

Earl "létra"
Csúcsok 2n
borda n+2(n-1)
Kromatikus szám 2
Kromatikus index 3 n>2
esetén 2 n=2
esetén 1 n=1 esetén
Tulajdonságok
Hamilton egységnyi távolság gráf
sík
bipartit
Kijelölés L n
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben az L n létra egy síkbeli irányítatlan gráf , amelynek 2n csúcsa és n+2(n-1) éle van [1] .

A létra két út közvetlen szorzataként kapható meg , amelyek közül az egyiknek csak egy éle van - L n = P n × P 1 [2] [3] . Ha hozzáadunk még két egymást metsző élt, amelyek egy második fokozatú létra négy csúcsát összekötik, akkor egy köbös gráfot kapunk - a Möbius-létrát .

Az L n létra felépítése szerint izomorf a G 2, n ráccsal , és úgy néz ki, mint egy n lépcsős létra. A gráf Hamilton -féle, kerülete 4 (ha n>1 ) és kromatikus indexe 3 (ha n>2 ).

A létra kromatikus száma 2, kromatikus polinomja pedig .

Ring létra grafikon

A CL n gyűrűlétragráf egy n≥3 hosszúságú ciklus és egy él közvetlen szorzata [4] . Szimbolikus formában CL n = C n × P 1 . A gráfnak 2n csúcsa és 3n éle van. A létrákhoz hasonlóan a gráfok is összefüggőek , síkbeliek és Hamilton - féleek , de a gráf akkor és csak akkor bipartit , ha n páros.

Galéria

Jegyzetek

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

Irodalom