Folkman gróf
| Folkman gróf | |
|---|---|
| Folkman gróf | |
| Valaki után elnevezve | J. Folkman |
| Csúcsok | húsz |
| borda | 40 |
| Sugár | 3 |
| Átmérő | négy |
| Heveder | négy |
| Automorfizmusok | 3840 |
| Kromatikus szám | 2 |
| Kromatikus index | négy |
| Tulajdonságok |
Bipartite Hamiltoni félszimmetrikus reguláris Euler Perfect |
| Médiafájlok a Wikimedia Commons oldalon | |
A Folkman-gráf (John Folkmanről kapta a nevét) egy kétrészes 4 - reguláris gráf, 20 csúcsgal és 40 éllel [1] .
A Folkman-gráf hamiltoni gráf , kromatikus száma 2, kromatikus indexe 4, sugara 3, átmérője 4 és kerülete 4. Ezenkívül 4-es csúcshoz , él-4-hez kapcsolódik és tökéletes . A gráf 3. könyvbeágyazást és 2. sorszámot tartalmaz [2] .
Algebrai tulajdonságok
A Folkman-gráf automorfizmuscsoportja tranzitívan hat az éleire, de nem a csúcsaira. Ez a legkisebb irányítatlan gráf, amely éltranzitív és szabályos, de nem csúcstranzitív [3] . Az ilyen gráfokat félszimmetrikusnak nevezik , először Folkman tanulmányozta őket 1967-ben, és felfedezett egy 20 csúcsú gráfot, amelyet később róla neveztek el [4] .
Félszimmetrikus gráfként a Folkman-gráf kétrészes , és automorfizmuscsoportja tranzitív módon hat a kétrészes gráf csúcsainak minden töredékére. Az alábbi diagramon, amely egy gráf kromatikus számát mutatja, a zöld csúcsok semmilyen automorfizmussal nem képezhetők le pirosra, de bármelyik vörös csúcs leképezhető bármely másik vörös csúcsra, és bármely zöld csúcs bármely másik zöld csúcsra.
A Folkman-gráf karakterisztikus polinomja : .
Galéria
-
A Folkman-gráf kromatikus indexe 4.
-
Folkman gróf kromatikus száma 2.
-
A Folkman-gráf Hamilton -féle .
Jegyzetek
- ↑ Weisstein, Eric W. Folkman grafikonja a Wolfram MathWorld weboldalán .
- ↑ Volz, 2018 .
- ↑ Skiena, 1990 , p. 186-187.
- ↑ Folkman, 1967 , p. 215–232.
Irodalom
- Skiena S. A diszkrét matematika megvalósítása: Kombinatorika és gráfelmélet a Mathematicával. Olvasás. – MA: Addison-Wesley, 1990.
- Jessica Walz. Lineáris elrendezések tervezése SAT segítségével. - Tübingeni Egyetem, 2018. - (Mesterdolgozat).
- Folkman J. Szabályos vonalszimmetrikus gráfok // Journal of Combinatorial Theory. - 1967. - T. 3 , szám. 3 . - doi : 10.1016/S0021-9800(67)80069-3 .