Earl of Holt
| Earl of Holt | |
|---|---|
| Holt-graafissa kaikki kärjet ovat ekvivalentteja ja kaikki reunat ovat ekvivalentteja, mutta ei ole automorfismia, joka kartoittaa reunan itselleen kärkien permutaatiolla | |
| Nimetty | Derek F. Holt |
| Huiput | 27 |
| kylkiluut | 54 |
| Säde | 3 |
| Halkaisija | 3 |
| Ympärysmitta | 5 |
| Automorfismit | 54 |
| Kromaattinen numero | 3 |
| Kromaattinen indeksi | 5 |
| Ominaisuudet |
vertex-transitiivinen reuna-transitiivinen puolitransitiivinen Hamiltonin Euler Cayley -graafi |
| Mediatiedostot Wikimedia Commonsissa | |
Holt -graafi tai Doyle-graafi on pienin puolitransitiivinen graafi , eli pienin esimerkki huipputransitiivisestä ja reunatransitiivisestä graafista, joka ei ole symmetrinen [1] [2] . Tällaisia kaavioita ei usein löydy [3] . Kaavio on nimetty Peter J. Doylen ja Derek F. Holtin mukaan, jotka löysivät graafin itsenäisesti vuonna 1976 [4] ja vuonna 1981 [5] .
Holt-graafin halkaisija on 3, säde 3 ja ympärysmitta 5, kromaattinen luku 3, kromaattinen indeksi 5. Graafi on Hamiltonin ja 98 472 eri Hamiltonin sykliä [6] . Kaavio on yhdistetty 4 kärkipisteeseen ja 4 reunaan yhdistetty . Siinä on kirjan upotus 3 ja jonomäärä 3. [7]
Graafilla on automorfismiryhmä luokkaa 54 [6] . Tämä on pienin ryhmä symmetrisille graafiille, joissa on sama määrä pisteitä ja reunoja. Kuvaajan piirros oikealla korostaa graafin peilisymmetrian puutetta.
Graafin ominaispolynomi on
Galleria
-
Holt-graafin kromaattinen indeksi on 5.
-
Holt-graafi on Hamiltonin .
Muistiinpanot
- ↑ Doyle, 1985 .
- ↑ Alspach, Marušič, Nowitz, 1994 , s. 391–402.
- ↑ Gross, Yellen, 2004 , s. 491.
- ↑ Doyle, 1976 .
- ↑ Holt, 1981 , s. 201–204.
- ↑ 1 2 Weisstein, Eric W. Doyle Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .
- ↑ Jessica Wolz, Lineaaristen asettelujen suunnittelu SAT:n kanssa . Diplomityö, Tübingenin yliopisto, 2018
Kirjallisuus
- Peter G. Doyle. 27-pisteinen kaavio, joka on kärkitranssitiivisesti ja reunatranssitiivisesti muttei L-transitiivinen. - 1985. - lokakuu. - arXiv : math/0703861 .
- Brian Alspach, Dragan Marusic, Lewis Nowitz. ½-transsitiivisten kaavioiden rakentaminen // Australian Mathematical Societyn lehti (A-sarja). - 1994. - T. 56 , no. 3 . - doi : 10.1017/S1446788700035564 . Arkistoitu alkuperäisestä 27. marraskuuta 2003.
- Jonathan L. Gross, Jay Yellen. Graafiteorian käsikirja. - CRC Press, 2004. - ISBN 1-58488-090-2 .
- Doyle PG Transitiivisissa kaavioissa. - Harvard College, 1976. - (Senior Thesis).
- Derek F. Holt. Kuvaaja, joka on reunatransitiivinen, mutta ei kaaritransitiivinen // Journal of Graph Theory . - 1981. - V. 5 , no. 2 . - doi : 10.1002/jgt.3190050210 .
- Jessica Walz. Lineaaristen asettelujen suunnittelu SAT:n avulla. - Tübingenin yliopisto, 2018. - (Pro gradu).