Franklin grófja
| Franklin grófja | |
|---|---|
| Valaki után elnevezve | Franklin |
| Csúcsok | 12 |
| borda | tizennyolc |
| Sugár | 3 |
| Átmérő | 3 |
| Heveder | négy |
| Automorfizmusok | 48 ( Z / 2 Z × S 4 ) |
| Kromatikus szám | 2 |
| Kromatikus index | 3 |
| Nemzetség | egy |
| Tulajdonságok |
Cubic Hamiltoni Bipartite Nincs háromszög Tökéletes Csúcs-tranzitív |
| Médiafájlok a Wikimedia Commons oldalon | |
A gráfelméletben a Franklin-gráf egy 3 - reguláris gráf , 12 csúcsgal és 18 éllel [1] .
A gráf Philip Franklin nevéhez fűződik , aki megcáfolta Heawood sejtését a cellákra osztott kétdimenziós felületek színezéséhez szükséges színek számáról a gráf beágyazásakor [2] [3] . Heawood sejtése szerint egy Klein-palackon a térkép maximális kromatikus száma hét legyen, de Franklin bebizonyította, hogy hat szín mindig elegendő egy adott gráfhoz. A Franklin-gráf beágyazható egy Klein-palackba, így hat színt igénylő kártyát alkot, ami azt mutatja, hogy bizonyos esetekben hat szín is elegendő. Ez a beágyazás a projektív síkban történő beágyazás Petri-duálisa (a beágyazás lent látható).
A gráf Hamilton -féle, kromatikus száma 2, kromatikus indexe 3, sugara 3, átmérője 3 és kerülete 4. Ez is egy 3 csúcshoz és 3 élhez kapcsolódó tökéletes gráf .
Algebrai tulajdonságok
A Franklin-gráf automorfizmuscsoportja 48-as rendű, és izomorf Z /2 Z × S 4 -el , amely a Z / 2 Z ciklikus csoport és az S 4 szimmetrikus csoport közvetlen szorzata . A csoport tranzitív módon hat a gráf csúcsaira.
A Franklin-gráf karakterisztikus polinomja az
Galéria
-
Franklin gróf kromatikus száma 2.
-
Franklin gróf kromatikus indexe 3.
-
Franklin gróf alternatív rajza.
-
A projektív síkban csonka féloktaéderként beágyazott Franklin-gráf .
Jegyzetek
- ↑ Weisstein, Eric W. Franklin Graph a Wolfram MathWorld webhelyen .
- ↑ Weisstein, Eric W. Heawood sejtése a Wolfram MathWorld weboldalán .
- ↑ Franklin, 1934 , p. 363-379.
Irodalom
- P. Franklin. Hat szín probléma // J. Math. Fizik.. - 1934. - T. 13 . - S. 363-379 .