thumb|right|200px|Tuttejeva (3,8)-kletka.
Klétka je v teoriji grafov regularni graf, ki ima za svoj dani notranji obseg najmanjše možno število točk.
Formalno je (r,g)-graf določen kot graf v katerem ima vsaka točka točno r sosednjih točk, in v katerem ima najkrajši cikel dolžino točno g. Znano je, da (r,g)-graf obstaja za vsako kombinacijo r ≥ 2 in g ≥ 3. (r,g)-kletka je (r,g)-graf z najmanjšim možnim številom točk med vsemi (r,g)-grafi.
Če obstaja Mooreov graf stopnje r in notranjim obsegom g, mora biti kletka. Velja še naprej, meje velikosti Mooreovih grafov se posplošijo na kletke. Vsaka kletka z lihim notranjim obsegom g mora imeti vsaj:
točk, in vsaka kletka s sodim notranjim obsegom g mora imeti vsaj:
točk. Vsak (r,g)-graf s točno toliko točkami je po definiciji Mooreov graf in s tem tudi kletka.
Za dano kombinacijo r in g lahko obstaja več kletk. Obstajajo na primer tri neizomorfne (3,10)-kletke, vsaka s 70 točkami: Balabanova 10-kletka, Harriesov graf in Harries-Wongov graf. Obstaja pa le ena (3,11)-kletka: Balabanova 11-kletka (s 112 točkami).
Znane kletke
Graf stopnje 1 nima cikla, notranji obseg povezanih grafov stopnje 2 je enak številu njihovih točk, tako da so zanimive le kletke za r ≥ 3. (r,3)-kletka je polni graf Kr+1 na r+1 točkah, (r,4)-kletka pa je polni dvodelni graf Kr,r na 2r točkah.
Druge pomembne kletke vsebujejo Mooreove grafe:
(3,5)-kletka: Petersenov graf, 10 točk (3,6)-kletka: Heawoodov graf, 14 točk (3,8)-kletka: Tutte-Coxetrov graf, 30 točk (7,5)-kletka: Hoffman-Singletonov graf, 50 točk.
Število točk v znanih (r,g)-kletkah za vrednosti r > 2 in g > 2, so: g: 3 4 5 6 7 8 9 10 11 12 r = 3: 4 6 10 14 24 30 58 70 112 126 r = 4: 5 8 19 26 67 80 728 r = 5: 6 10 30 42 170 2730 r = 6: 7 12 40 62 312 7812 r = 7: 8 14 50 90
Zunanje povezave
Brouwer, Andries Evert, Cages
Kategorija:Družine grafov Kategorija:Regularni grafi