Graf Wiener – Araya - Wiener–Araya graph

Graf Wiener-Araya
Wiener-Araya.svg
Vrcholy42
Hrany67
Poloměr5
Průměr7
Obvod4
Automorfismy2
Chromatické číslo3
Chromatický index4
VlastnostiHypohamiltoniá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

  1. ^ Sousselier, R. (1963), Problém č. 29: Le cercle des irascibles, 7, Rev. Franç. Rech. Opérationnelle, str. 405–406
  2. ^ 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
  3. ^ Gaudin, T .; Herz, P .; Rossi (1964), „Solution du problème č. 29“, Rev. Franç. Rech. Opérationnelle (francouzsky), 8: 214–218
  4. ^ Busacker, R. G .; Saaty, T. L. (1965), Konečné grafy a sítě
  5. ^ 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
  6. ^ 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
  7. ^ 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
  8. ^ 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
  9. ^ Wiener, Gábor; Araya, Makoto (20. dubna 2009), Konečná otázka, arXiv:0904.3012, Bibcode:2009arXiv0904,3012W.
  10. ^ 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.

externí odkazy