Kletka (teorija grafov)

Klétka je v teoriji grafov regularni graf, ki ima za svoj dani notranji obseg najmanjše možno število točk.

Tuttejeva (3,8)-kletka.

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:

$1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}\!\,$

točk, in vsaka kletka s sodim notranjim obsegom g mora imeti vsaj:

$2\sum _{i=0}^{(g-2)/2}(r-1)^{i}\!\,$

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 K_r+1 na r+1 točkah, (r,4)-kletka pa je polni dvodelni graf K_r,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 (angleško)
• Weisstein, Eric Wolfgang. »Cage Graph«. MathWorld.