Cell (gráfelmélet)
Az n-cella egy n kerületű , a lehető legkisebb csúcsszámú köbös gráf . Egy gráfot köbösnek nevezünk, ha minden csúcsából 3 él emelkedik ki. A gráf kerülete a benne lévő legkisebb ciklus hossza.
Minden 2 < n < 9 esetén van egy egyedi n-cella, és ezek a gráfok erősen szimmetrikusak ( egytranzitívak ). Ezenkívül, ha síkon ábrázolják, gyakran extrém számú önmetszéspontot adnak meg, a továbbiakban önmetszési indexnek .
- 3 cellás - K 4 , tetraéder gerince , 4 csúcs.
- 4 cellás - K 3,3 , a két minimális nem síkbeli gráf egyike, 6 csúcs.
- 5 cellás - Petersen gráf , 10 csúcs. Minimális köbös grafikon 2-es önmetszési indexszel.
- 6 cellás - Heawood gráf , 14 csúcs. 1-tényezőkre bontva (azaz élszínűre) két tényező tetszőleges összege Hamilton-ciklust alkot . Minimális köbös grafikon 3-as önmetszési indexszel.
- 7 cellás - McGee gróf , 24 csúcs. Minimális köbös grafikon 8-as önmetszési indexszel.
- 8 cellás - Gróf Tatta - Coxeter , 30 csúcs.
Általános meghatározás
Az ( r , n )-cella egy r fokú (azaz minden csúcsnak pontosan r éle) és n kerületű , a lehető legkisebb csúcsszámú szabályos gráf.
Triviális családok
- A (2, n )-cellák nyilvánvalóan ciklikus C n gráfok
- Az ( r -1,3)-cellák r csúcsok teljes K r gráfjai
- Az ( r ,4)-cellák teljes kétrészes gráfok К r , r , amelyek mindegyik részében r csúcs található
Nem triviális képviselők
- (7,5)-cella - Hoffman-Singleton gráf , 50 csúcs.
Még néhány sejt ismert. Az alábbi táblázat a 3≤ r ≤7 fokú és 3≤ n ≤12 kerületű ( r , n )-cellák csúcsainak számát mutatja . Az ezekhez és a nagyobb r és n cellák leírása itt található: [1] (angolul).
| n : | 3 | négy | 5 | 6 | 7 | nyolc | 9 | tíz | tizenegy | 12 |
| r = 3: | négy | 6 | tíz | tizennégy | 24 | harminc | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | nyolc | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r = 5: | 6 | tíz | harminc | 42 | 152 | 170 | 2730 | |||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r = 7: | nyolc | tizennégy | ötven | 90 |
Moore grófjai
Az ( r , n ) -cellában lévő csúcsok száma nagyobb vagy egyenlő, mint
páratlan n -re és méghozzá.
Ha az egyenlőség fennáll, akkor a megfelelő gráfot Moore-gráfnak nevezzük . Bár minden r > 2 és n > 2 esetén létezik cella, sokkal kevesebb a nem triviális Moore-gráf. A fenti cellák közül a Moore-gráfok a Petersen -gráf, a Heawood-gráf , a Tutt-Coxeter- gráf és a Hoffman-Singleton-gráf. Bebizonyosodott [1] [2] [3] , hogy minden páratlan esetet kimerít n = 5, r = 2, 3, 7 és esetleg 57, a páros eseteket pedig n = 6, 8, 12.
Jegyzetek
- ↑ Bannai, E. és Ito, T. "On Moore Graphs." J. Fac. sci. Univ. Tokyo Ser. A 20, 191-208, 1973
- ↑ Damerell, R.M. „A Moore Graphs-on”. Proc. Cambridge Philos. szoc. 74, 227-236, 1973
- ↑ Hoffman, AJ és Singleton, RR "On Moore Graphs of Diameter 2 and 3." IBM J. Res. Fejleszteni. 4, 497-504, 1960
Irodalom
- F. Harari gráfelmélet . - M .: URSS , - 2003. - 300 s - ISBN 5-354-00301-6 .
Linkek
- Weisstein, Eric W. Cell Graph , Wolfram MathWorld .
- https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/ _