Kreivi Goldner - Harari

Graafiteoriassa Goldner-Harari-graafi on  yksinkertainen suuntaamaton graafi , jossa on 11 kärkeä ja 27 reunaa. Tiedosto on nimetty A. Goldnerin ja F. Hararin mukaan, jotka vuonna 1975 osoittivat olevansa pienin ei-Hamiltonin maksimaalinen tasograafi [1] [2] [3] . Grünbaum antoi saman graafin esimerkkinä ei-Hamiltonin yksinkertaisesta polytooppista jo vuonna 1967. [4]

Ominaisuudet

Goldner-graafi on Hararin tasomainen  - se voidaan piirtää tasolle ilman, että se ylittää reunoja. Kun piirretään tasolle, kaikki kaavion pinnat ovat kolmion muotoisia, mikä tekee siitä maksimaalisen tasograafin . Kuten mikä tahansa maksimaalinen tasograafi, se on myös 3-vertex-kytketty  - kahden pisteen poistaminen jättää aligraafin yhteen .

Earl of Goldner on ei-hamiltonilaisten harari . Pienin mahdollinen pistemäärä ei-Hamiltonin monitahoisille graafille on 11. Näin ollen Goldner-Hararin graafi on esimerkki tämän tyyppisestä minimaalisesta graafista. Kuitenkin Herschel Graph , toinen ei-Hamiltonin monitahoinen 11 kärkeä, on vähemmän reunoja.

Maksimaalisena tasomaisena ei-Hamiltonin graafina Goldner-Harari-graafi tarjoaa esimerkin tasograafista, jonka kirjan paksuus on suurempi kuin kaksi [5] . Tällaisten esimerkkien olemassaolon perusteella Bernhart ja Kainen (Bernhart, Kainen) olettivat, että tasograafien kirjan paksuus voi olla mielivaltaisen suuri, mutta sitten osoitettiin, että kaikkien tasograafien kirjan paksuus ei ylitä neljää [6] .

Graafin kirjan paksuus on 3, kromaattinen luku 4, kromaattinen indeksi 8, ympärysmitta 3, säde 2, halkaisija 2 ja graafi on 3-särmäinen .

Graafi on myös 3-puu , joten sen puunleveys on 3. Kuten mikä tahansa k - puu, graafi on sointu . Tasomaisena 3-puuna kuvaaja tarjoaa esimerkin Apollonius-verkosta .

Geometria

Steinitzin lauseen mukaan Goldner-Harari-graafi on monitahoinen graafi  - se on tasomainen ja 3-liittynyt, joten on kupera monitahoinen, jonka luuranko on Goldner-Harari-graafi .

Geometrisesti Goldner-Harari-graafin monitahoinen esitys voidaan muodostaa liimaamalla tetraedri kolmion muotoisen bipyramidin jokaiselle pinnalle , samalla tavalla kuin kolmiulotteinen tetraedri muodostetaan liimaamalla tetraedri oktaedrin jokaiseen pintaan . Eli se on kolmiomaisen dipyramidin Kleen monitahoinen [4] [7] . Kreivi Goldner-Hararin kaksoisgraafi on geometrisesti esitetty kolmiomaisen prisman katkaisulla .

Algebralliset ominaisuudet

Goldner-Hararin graafin automorfismiryhmällä on luokkaa 12 ja se on isomorfinen dihedraalisen ryhmän D 6 kanssa, säännöllisen kuusikulmion symmetriaryhmän kanssa, joka sisältää sekä rotaatiot että heijastukset.

Goldner-Harari-graafin ominaispolynomi on .

Muistiinpanot

1. ↑ A. Goldner, F. Harary. {{{title}}} // Bull. Malesian matematiikka. Soc.. - 1975. - V. 6 , no. 1 . - S. 41-42 . . Katso myös numerot 6 (2):33 (1975) ja 8 :104-106 (1977). Linkkejä Hararin julkaisujen sivustoluettelosta Arkistoitu 2. tammikuuta 2013 Wayback Machinessa .
2. ↑ M. B. Dillencourt. Pienten tilausten polyhedrat ja niiden Hamiltonin ominaisuudet // Journal of Combinatorial Theory, sarja B. - 1996. - V. 66 . — S. 87–122 . - doi : 10.1006/jctb.1996.0008 . .
3. ↑ RC Read, RJ Wilson. Graafisten atlas. - Oxford, Englanti: Oxford University Press, 1998. - S. 285. .
4. ↑ 1 2 Branko Grünbaum. Kuperat polytoopit. - Wiley Interscience, 1967. - S. 357. .
5. ↑ Frank R. Bernhart, Paul C. Kainen. Kirjan kaavion paksuus. - Journal of Combinatorial Theory, sarja B. - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
6. ↑ Mihalis Yanakakis. Proc. 18th ACM Symp. Tietojenkäsittelyteoria (STOC). - 1986. - S. 104-108. - doi : 10.1145/12130.12141 . .
7. ↑ Gunther Ewald. Hamiltonin piirit yksinkertaisissa komplekseissa // Geometriae Dedicata. - 1973. - Osa 2 , numero. 1 . — S. 115–125 . - doi : 10.1007/BF00149287 . .

Linkit

• Weisstein, Eric W. Goldner-Harary -kaavio  (englanniksi) Wolfram MathWorld -verkkosivustolla .