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 K4 teljes gráf (3,4)-cage a K4,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:A jelenleg ismert cage gráfok, és a nem ismertek csúcsszámára vonatkozó becslések Az (r,3)-cage a Kr+1 teljes gráf Az (r,4)-cage a Kr,r teljes páros gráf
Jegyzetek
Források Wolfram MathWorld Cage Graph Brouwer, Andries E. Cage
Kategória:Gráfelmélet