Folkmanův graf - Folkman graph
Folkmanův graf | |
---|---|
Folkmanův graf | |
Pojmenoval podle | Jon Folkman |
Vrcholy | 20 |
Hrany | 40 |
Poloměr | 3 |
Průměr | 4 |
Obvod | 4 |
Automorfismy | 3840 |
Chromatické číslo | 2 |
Chromatický index | 4 |
Tloušťka knihy | 3 |
Číslo fronty | 2 |
Vlastnosti | Hamiltonian Pravidelný Bipartitní Polosymetrické Eulerian Perfektní |
Tabulka grafů a parametrů |
V matematický pole teorie grafů, Folkmanův graf, pojmenoval podle Jon Folkman, je bipartitní 4-pravidelný graf s 20 vrcholy a 40 hran.[1]
Folkmanův graf je Hamiltonian a má chromatické číslo 2, chromatický index 4, poloměr 3, průměr 4 a obvod 4. Je to taképřipojen k vrcholu a 4-připojeno k okraji perfektní graf. Má to tloušťka knihy 3 a číslo fronty 2.[2]
Algebraické vlastnosti
The skupina automorfismu Folkmanova grafu působí přechodně na jeho hrany, ale ne na jeho vrcholy. Je to nejmenší neorientovaný graf, který je hrana tranzitivní a pravidelné, ale ne vrchol-tranzitivní.[3] Takové grafy se nazývají polosymetrické grafy a byly poprvé studovány Folkmanem v roce 1967, který objevil graf na 20 vrcholech, který je nyní pojmenován po něm.[4]
Jako polosymetrický graf je Folkmanův graf bipartitní a jeho skupina automorfismu působí přechodně na každou ze dvou vertexových sad bipartice. V níže uvedeném diagramu označujícím chromatické číslo grafu nelze zelené vrcholy mapovat na červené žádným automorfismem, ale libovolný červený vrchol lze mapovat na jakýkoli jiný červený vrchol a jakýkoli zelený vrchol lze mapovat na jakýkoli jiný zelený vrchol .
The charakteristický polynom Folkmanova grafu je .
Galerie
The chromatický index Folkmanova grafu je 4.
The chromatické číslo Folkmanova grafu je 2.
Folkmanův graf je Hamiltonian.
Reference
- ^ Weisstein, Eric W. "Folkmanův graf". MathWorld.
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Skiena, S. Implementace diskrétní matematiky: Kombinatorika a teorie grafů s Mathematica. Reading, MA: Addison-Wesley, str. 186-187, 1990
- ^ Folkman, J. (1967), "Pravidelné řádkově symetrické grafy", Journal of Combinatorial Theory, 3 (3): 215–232, doi:10.1016 / S0021-9800 (67) 80069-3