Cage (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
(3-6)-cage
Heawood Graph.svg
Heawood-gráf

Névadó Percy John Heawood
Csúcsok száma 14
Élek száma 21
Átmérő 3
Kromatikus szám 2
Élkromatikus szám 3

Egy cage-gráf egy olyan reguláris gráf, amelynek a lehető legkevesebb csúcsa van, adott girth paraméter mellett.

Tehát egy (r,g)-cage olyan gráf ahol minden fokszám r és a gráfban található legrövidebb kör hossza g. Minden r ≥ 2 és g ≥ 3 esetén létezik r-reguláris g-girth paraméterű gráf, ezek közül a legkevesebb csúccsal rendelkezőket hívjuk (r,g)-cage gráfoknak.

Adott r és g esetén létezhet több (r,g)-cage, például három nem izomorf (3,10)-cage létezik.

Ismert cage-k[szerkesztés | forrásszöveg szerkesztése]

r=1 esetén egy gráf nem tartalmazhat kört, így szükségképpen girth paramétere végtelen.

r=2 esetén a gráf körök uniója lehet csak, így girth paramétere a legkisebb kör hossza, de mivel a lehető legkevesebb csúcsot tartalmazza, ezért a (2,g)-cage gráfok g hosszú körök.

Tetszőleges r esetén:[1]

r=3 esetén már számos cage-t ismerünk, az első néhány:[2]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. A jelenleg ismert cage gráfok, és a nem ismertek csúcsszámára vonatkozó becslések[1]
  2. az ismert 3-reguláris cage gráfok g=32 ig

Források[szerkesztés | forrásszöveg szerkesztése]