Pěstounský graf - Foster graph
| Pěstounský graf | |
|---|---|
 Fosterův graf | |
| Pojmenoval podle | Ronald Martin Foster |
| Vrcholy | 90 |
| Hrany | 135 |
| Poloměr | 8 |
| Průměr | 8 |
| Obvod | 10 |
| Automorfismy | 4320 |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Krychlový Bipartitní Symetrický Hamiltonian Přechodná vzdálenost |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Pěstounský graf je bipartitní 3-běžný graf s 90 vrcholy a 135 hranami.[1]
Fosterův graf je Hamiltonian a má chromatické číslo 2, chromatický index 3, poloměr 8, průměr 8 a obvod 10. Je to také 3-připojen k vrcholu a 3-připojeno k okraji graf. Má to číslo fronty 2 a horní mez na tloušťka knihy je 4.[2]
Všechny krychlový vzdálenost-pravidelné grafy jsou známy.[3] Fosterův graf je jedním ze 13 takových grafů. Je to jedinečný vzdálenost-tranzitivní graf s průnikové pole {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}.[4] Může být konstruován jako graf výskytu z částečný lineární prostor což je jedinečný triple Pokrýt bez 8-gonů zobecněný čtyřúhelník GQ(2,2). Je pojmenován po R. M. Foster, jehož Podporovat sčítání lidu z krychlový symetrické grafy zahrnoval tento graf.
The bipartitní polovina Fosterova grafu je a vzdálenost-pravidelný graf a a lokálně lineární graf. Je to jeden z konečného počtu takových grafů se stupněm šest.[5]
Algebraické vlastnosti
Skupina automorfismu Fosterova grafu je skupina řádu 4320.[6] Působí přechodně na vrcholy, na hrany a na oblouky grafu. Fosterův graf je tedy a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Fosterův graf, označovaný jako F90A, je jediný kubický symetrický graf na 90 vrcholech.[7]
The charakteristický polynom Fosterova grafu se rovná .
Galerie
Fosterový graf barevně zvýrazňuje různé cykly.
The chromatické číslo Fosterova grafu je 2.
The chromatický index Fosterova grafu je 3.
Reference
- ^ Weisstein, Eric W. „Foster Graph“. MathWorld.
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Brouwer, A.E .; Cohen, A. M .; a Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ^ Kubické vzdálenosti - pravidelné grafy, A. Brouwer.
- ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), „Vzdálené pravidelné grafy valence 6 a ", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023 / A: 1008776031839, PAN 1761910
- ^ Royle, G. Data F090A[trvalý mrtvý odkaz ]
- ^ Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.
- Biggs, N.L .; Boshier, A. G .; Shawe-Taylor, J. (1986), „Kubické vzdálenosti - pravidelné grafy“, Journal of the London Mathematical Society, 33 (3): 385–394, doi:10.1112 / jlms / s2-33.3.385, PAN 0850954.
- Van Dam, Edwin R .; Haemers, Willem H. (2002), „Spektrální charakterizace některých pravidelných grafů vzdálenosti“, Journal of Algebraic Combinatorics, 15 (2): 189–202, doi:10.1023 / A: 1013847004932, PAN 1887234.
- Van Maldeghem, Hendrik (2002), „Deset výjimečných geometrií z pravidelných grafů trivalentní vzdálenosti“, Annals of Combinatorics, 6 (2): 209–228, doi:10.1007 / PL00012587, PAN 1955521.