Graf Wiener – Araya - Wiener–Araya graph
Graf Wiener-Araya | |
---|---|
![]() | |
Vrcholy | 42 |
Hrany | 67 |
Poloměr | 5 |
Průměr | 7 |
Obvod | 4 |
Automorfismy | 2 |
Chromatické číslo | 3 |
Chromatický index | 4 |
Vlastnosti | Hypohamiltonián Rovinný |
Tabulka grafů a parametrů |
The Graf Wiener – Araya je v teorie grafů, graf na 42 vrcholech se 67 hranami. to je hypohamiltonián, což znamená, že to samo o sobě nemá Hamiltonovský cyklus ale každý graf vytvořený odstraněním jediného vrcholu z něj je Hamiltonian. Je to také rovinný.
Dějiny
Hypohamiltonovské grafy byly nejprve studovány Sousselierem v Problèmes plaisantset délectables (1963).[1]V roce 1967 Lindgren sestavil nekonečnou sekvenci hypohamiltonovských grafů.[2]Nejprve uvádí Gaudina, Herze a Rossiho,[3] pak Busacker a Saaty[4]jako průkopníci v tomto tématu.
Od začátku nejmenší hypohamiltoniánský graf je známo: Petersenův graf. Hon na ty nejmenší rovinný hypohamiltoniánský graf pokračuje. Tuto otázku poprvé položil Václav Chvátal v roce 1973.[5]Odpověď poskytuje v roce 1976 Carsten Thomassen, který vykazuje konstrukci 105 vrcholů, 105-Thomassenův graf.[6]V roce 1979 Hatzel vylepšuje tento výsledek o a rovinný hypohamiltoniánský graf na 57 vrcholech: Hatzelův graf.[7]Tato hranice je v roce 2007 snížena o 48-Zamfirescuův graf.[8]
V roce 2009 se graf vytvořený Gáborem Wienerem a Makoto Arayou stává (se 42 vrcholy) nejmenším rovinný hypohamiltoniánský graf známý.[9][10]Wiener a Araya ve svém příspěvku předpokládají, že jejich grafy jsou optimální a tvrdí, že jejich pořadí (42 ) se jeví jako odpověď na The Ultimate Question of Life, the Universe, and Everything z Stopařův průvodce po Galaxii, a Douglas Adams román.
Reference
- ^ Sousselier, R. (1963), Problém č. 29: Le cercle des irascibles, 7, Rev. Franç. Rech. Opérationnelle, str. 405–406
- ^ Lindgren, W. F. (1967), „Nekonečná třída hypohamiltonovských grafů“, Americký matematický měsíčník, 74: 1087–1089, doi:10.2307/2313617, PAN 0224501
- ^ Gaudin, T .; Herz, P .; Rossi (1964), „Solution du problème č. 29“, Rev. Franç. Rech. Opérationnelle (francouzsky), 8: 214–218
- ^ Busacker, R. G .; Saaty, T. L. (1965), Konečné grafy a sítě
- ^ Chvátal, V. (1973), „Flip-flops in hypo-Hamiltonian graphs“, Kanadský matematický bulletin, 16: 33–41, doi:10.4153 / cmb-1973-008-9, PAN 0371722
- ^ Thomassen, Carsten (1976), „Planární a nekonečné hypohamiltonovské a hypotrakovatelné grafy“, Diskrétní matematika, 14 (4): 377–389, doi:10.1016 / 0012-365x (76) 90071-6, PAN 0422086
- ^ Hatzel, Wolfgang (1979), „Ein planarer hypohamiltonscher Graph mit 57 Knoten“, Mathematische Annalen (v němčině), 243 (3): 213–216, doi:10.1007 / BF01424541, PAN 0548801
- ^ Zamfirescu, Carol T .; Zamfirescu, Tudor I. (2007), "Planární hypohamiltoniánský graf se 48 vrcholy", Journal of Graph Theory, 55 (4): 338–342, doi:10.1002 / jgt.20241, PAN 2336805
- ^ Wiener, Gábor; Araya, Makoto (20. dubna 2009), Konečná otázka, arXiv:0904.3012, Bibcode:2009arXiv0904,3012W.
- ^ Wiener, Gábor; Araya, Makoto (2011), „On planar hypohamiltonian graphs“, Journal of Graph Theory, 67 (1): 55–68, doi:10.1002 / jgt.20513, PAN 2809563.