Cage (gráfelmélet)

(3-6)-cage
Heawood-gráf
Névadó	Percy John Heawood
Csúcsok száma	14
Élek száma	21
Sugár	3
Átmérő	3
Derékbőség	6
Kromatikus szám	2
Élkromatikus szám	3
Automorfizmusok	336
Génusz	1

Azokat a speciális gráfokat nevezzük cage-nek (kalitkának) amelyek reguláris gráfok, és egy rögzített girth (a legrövidebb kör a gráfban) mellett a lehető legkevesebb csúcsuk van.

Tehát az (r,g)-cage-k speciális elemei annak a gráfcsaládnak amik azokból a gráfokból állnak 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 olyan gráf ami r-reguláris és amiben a girth éppen g. Mivel ezek közül a legkevesebb csúccsal rendelkezőket hívjuk (r,g)-cage gráfoknak, ezért ezekben az esetekben létezik is (r,g)-cage. Rögzített r és g esetén létezhet több (r,g)-cage is, például három nem izomorf (3,10)-cage létezik.

Ismert cage-ek

r=1 esetén egy gráf nem tartalmazhat kört, így semmilyen véges g esetén nincs (1,g)-cage.

r=2 esetén egy gráf csak diszjunkt körök uniója lehet. Ezekben az esetekben a girth nyilvánvalóan a legkisebb kör hossza. Mivel azokat a gráfokat nevezzük cage-nek, amik ilyen feltételek mellett a lehető legkevesebb csúcsot tartalmazzák, ezért a (2,g)-cage gráfok pontosan a g hosszú körök.

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

• (3,3)-cage a K₄ teljes gráf
• (3,4)-cage a K_4,4 teljes páros gráf
• (3,5)-cage a Petersen-gráf
• (3,6)-cage a Heawood-gráf (melynek a tóruszba való beágyazása a Szilassi-poliéder)
• (3,7)-cage a McGee-gráf
• (3,8)-cage az illeszkedési gráf (másik nevén a Tutte 8-cage)

Tetszőleges r esetén:

• Az (r,3)-cage a K_r+1 teljes gráf
• Az (r,4)-cage a K_r,r teljes páros gráf

Források

• Wolfram MathWorld Cage Graph
• Brouwer, Andries E. Cage