Hortonův graf - Horton graph
| Hortonův graf | |
|---|---|
 Hortonův graf | |
| Pojmenoval podle | Joseph Horton |
| Vrcholy | 96 |
| Hrany | 144 |
| Poloměr | 10 |
| Průměr | 10 |
| Obvod | 6 |
| Automorfismy | 96 (Z/2Z ×Z/2Z×S4 ) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Krychlový Bipartitní |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Hortonův graf nebo Horton 96 grafů je 3-běžný graf s 96 vrcholy a 144 hranami objevenými Josephem Hortonem.[1] Publikováno Bondym a Murtym v roce 1976 poskytuje protiklad k Tutteho domněnce, že každý krychlový 3 připojené bipartitní graf je Hamiltonian.[2][3]
Po Hortonově grafu byla nalezena řada menších protikladů k domněnce Tutte. Mezi nimi je 92 vrcholný graf od Hortona publikovaný v roce 1982, 78 vrcholový graf od Owense publikovaný v roce 1983 a dva Ellingham-Hortonovy grafy (Vrcholy 54 a 78).[4][5]
První Ellingham-Hortonův graf publikoval Ellingham v roce 1981 a měl pořadí 78.[6] V té době to byl nejmenší známý protiklad k domněnce Tutte. Druhý byl publikován Ellinghamem a Hortonem v roce 1983 a měl pořadí 54.[7] V roce 1989 byl objeven Georgesův graf, nejmenší v současné době známý ne-hamiltonovský 3-propojený kubický bipartitní graf, který obsahuje 50 vrcholů.[8]
Jako nehamiltonovský kubický graf s mnoha dlouhými cykly poskytuje Hortonův graf dobré měřítko pro programy, které hledají hamiltonovské cykly.[9]
Hortonův graf má chromatické číslo 2, chromatický index 3, poloměr 10, průměr 10, obvod 6, tloušťka knihy 3[10] a číslo fronty 2.[10] Je to také 3-hranový graf.
Algebraické vlastnosti
The automorfická skupina Hortonova grafu je řádu 96 a je izomorfní s Z/2Z×Z/2Z×S4, přímý produkt z Kleinova čtyřčlenná skupina a symetrická skupina S4.
The charakteristický polynom Hortonova grafu je: .
Galerie
The chromatické číslo Hortonova grafu je 2.
The chromatický index Hortonova grafu je 3.
The Ellingham-Horton 54-graf, menší protiklad k domněnce Tutte.
Reference
- ^ Weisstein, Eric W. „Hortonův graf“. MathWorld.
- ^ Tutte, W. T. „O 2-faktorech bikubických grafů“. Diskrétní matematika. 1, 203-208, 1971/72.
- ^ Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 240, 1976.
- ^ Horton, J. D. „O dvou faktorech bipartitních regulárních grafů.“ Diskrétní matematika. 41, 35-41, 1982.
- ^ Owens, P. J. „Bipartitní kubické grafy a krátký exponent.“ Diskrétní matematika. 44, 327 - 330, 1983.
- ^ Ellingham, M. N. „Non-Hamiltonovské 3-propojené kubické partitní grafy.“ Výzkumná zpráva č. 28, odbor Math., Univ. Melbourne, Melbourne, 1981.
- ^ Ellingham, M. N. a Horton, J. D. „Non-hamiltonovské 3-propojené kubické bipartitní grafy.“ J. Combin. Čt. Ser. B 34, 350-353, 1983.
- ^ Georges, J. P. (1989), „nehamiltonovské bikubické grafy“, Journal of Combinatorial Theory, Series B, 46 (1): 121–124, doi:10.1016/0095-8956(89)90012-9.
- ^ V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf „Efektivní algoritmus pro výčet okrajových barev a hamiltonovských cyklů v kubických grafech“ arXiv: math / 0610779v1.
- ^ A b Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018