Celle (grafteori)

En n-celle er en kubisk graf af omkreds n med det mindst mulige antal hjørner. En graf kaldes kubisk , hvis 3 kanter kommer frem fra hver af dens hjørner. Omkredsen af en graf er længden af den mindste cyklus i den.

For hver 2 < n < 9 er der en unik n-celle, og alle disse grafer er meget symmetriske ( unittransitive ). Når de er afbildet på et fly, giver de desuden ofte et ekstremt antal selvkryds, i det følgende benævnt selvkrydsningsindekset .

3-celle - K 4 , rygraden af et tetraeder , 4 hjørner.
4-celle - K 3,3 , en af de to minimale ikke - planære grafer, 6 hjørner.
5-celle - Petersen graf , 10 hjørner. Minimal kubisk graf med selvskæringsindeks 2.
6-celle - Heawood graf , 14 hjørner. Dekomponeret i 1-faktorer (det vil sige kantfarvet) danner enhver sum af to faktorer en Hamilton-cyklus . Minimal kubisk graf med selvskæringsindeks 3.
7-celler - Grev McGee , 24 hjørner. Minimal kubisk graf med selvskæringsindeks 8.
8-celler - Grev Tatta - Coxeter , 30 hjørner.

Generaliseret definition

( r , n )-celle er en regulær graf af grad r (det vil sige, at hvert toppunkt har nøjagtigt r kanter) og omkreds n med det mindst mulige antal hjørner.

Trivielle familier

(2, n )-celler er åbenbart cykliske grafer C n
( r -1,3)-celler er komplette grafer K r af r hjørner
( r ,4)-celler er komplette todelte grafer К r , r , som har r hjørner i hver del

Ikke-trivielle repræsentanter

(7,5)-celle - Hoffman-Singleton graf , 50 hjørner.

Nogle flere celler er kendt. Tabellen nedenfor viser antallet af hjørner i ( r , n )-celler med grad 3≤ r ≤7 og omkreds 3≤ n ≤12. Celler for disse og større r og n er beskrevet her: [1] (på engelsk).

r =3:	fire	6	ti	fjorten	24	tredive	58	70	112	126
n :	3	fire	5	6	7	otte	9	ti	elleve	12
r =4:	5	otte	19	26	67	80	275	384		728
r =5:	6	ti	tredive	42	152	170				2730
r =6:	7	12	40	62	294	312				7812
r =7:	otte	fjorten	halvtreds	90

Counts of Moore

Antallet af hjørner i ( r , n )-celle er større end eller lig med

{\displaystyle 1+r\sum _{i=0}^{(n-3)/2}(r-1)^{i))

for ulige n og

{\displaystyle 2\sum _{i=0}^{(n-2)/2}(r-1)^{i))

for endda.

Hvis lighed gælder, så kaldes den tilsvarende graf en Moore-graf . Mens en celle eksisterer for enhver r > 2 og n > 2, er der langt færre ikke-trivielle Moore-grafer. Af ovenstående celler er Moore-graferne Petersen - grafen, Heawood-grafen , Tutt - Coxeter- grafen og Hoffman-Singleton-grafen. Det er blevet bevist [1] [2] [3] at alle ulige tilfælde er udtømt med n = 5, r = 2, 3, 7 og muligvis 57, og lige tilfælde med n = 6, 8, 12.

Noter

↑ Bannai, E. og Ito, T. "On Moore Graphs." J. Fac. sci. Univ. Tokyo Ser. A 20, 191-208, 1973
↑ Damerell, R.M. "On Moore Graphs." Proc. Cambridge Philos. soc. 74, 227-236, 1973
↑ Hoffman, AJ og Singleton, RR "On Moore Graphs of Diameter 2 and 3." IBM J. Res. Udvikle. 4, 497-504, 1960

Litteratur

F. Harari grafteori . - M .: URSS , - 2003. - 300 s - ISBN 5-354-00301-6 .

Celle (grafteori)

Generaliseret definition

Counts of Moore

Noter

Litteratur

Links