Ladder (teorie grafů)

hrabě "žebřík"
Vrcholy 2n
žebra n+2(n-1)
Chromatické číslo 2
Chromatický index 3 pro n>2
2 pro n=2
1 pro n=1
Vlastnosti
Hamiltonovský jednotkový graf vzdálenosti
planární
bipartit
Označení L n
 Mediální soubory na Wikimedia Commons

V teorii grafů je žebřík L n rovinný neorientovaný graf s 2n vrcholy a n+2(n-1) hranami [1] .

Žebřík lze získat jako přímý součin dvou drah , z nichž jedna má pouze jednu hranu - L n = P n × P 1 [2] [3] . Přidáme-li další dvě protínající se hrany spojující čtyři vrcholy žebříku se stupněm dva, dostaneme kubický graf - Möbiův žebřík .

Konstrukčně je žebřík L n izomorfní k mřížce G 2, n a vypadá jako žebřík s n příčkami. Graf je hamiltonovský s obvodem 4 (pokud n>1 ) a chromatickým indexem 3 (pokud n>2 ).

Chromatické číslo žebříku je 2 a jeho chromatický polynom je .

Prstencový žebříkový graf

Kruhový žebříkový graf CL n je přímým součinem cyklu délky n≥3 a hrany [4] . V symbolickém tvaru CL n = C n × P 1 . Graf má 2n vrcholů a 3n hran. Stejně jako žebříky je graf souvislý , rovinný a hamiltonovský , ale graf je bipartitní právě tehdy, když n je sudé.

Galerie

Poznámky

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

Literatura