Grev Harris-Wong
| Grev Harris-Wong | |
|---|---|
| Toppe | 70 |
| ribben | 105 |
| Radius | 6 |
| Diameter | 6 |
| Omkreds | ti |
| Automorfismer | 24 ( S4 ) |
| Kromatisk tal | 2 |
| Kromatisk indeks | 3 |
| Ejendomme |
kubisk celle uden hamiltonske trekanter |
I grafteori er en Harris-Wong-graf en 3-regulær urettet graf med 70 hjørner og 105 kanter [1] .
Det kromatiske tal på grafen er 2, det kromatiske indeks er 3, grafens diameter og radius er 6, og omkredsen er 10.
Grafen er en Hamiltonsk , 3 -kant-forbundet , 3-kant-forbundet , plan kubisk graf.
Harris-Wong-grafens karakteristiske polynomium er
Historie
I 1972 udgav AT Balaban en (3-10) -celle , kubisk graf, der har det mindste antal hjørner for en omkreds på 10 [2] . Det var den første åbne (3-10)-celle, men den er ikke unik [3] .
En komplet liste over (3-10)-celler og bevis for minimalitet blev givet af O'Keefe og Wong i 1980 [4] . Der er kun tre forskellige (3-10)-celler - Balaban 10-cellen , Harris-grafen og Harris-Wong-grafen [5] . Desuden er Harris-Wong-grafen og Harris-grafen kospektrale grafer .
Galleri
-
Grev Harris-Wongs kromatiske tal er 2.
-
Harris-Wong-grafens kromatiske indeks er 3.
-
Alternativ tegning af grev Harris-Wong.
-
8 kredsløb af grev Harris - Wong.
Noter
- ↑ Weisstein, Eric W. Harries–Wong Graph på Wolfram MathWorld -webstedet .
- ↑ Balaban, 1972 , s. 1-5.
- ↑ Pisanski, Boben, Marusic, Orbanic, 2001 .
- ↑ O'Keefe, Wong, 1980 , s. 91-105.
- ↑ Bondy, Murty, 1976 , s. 237.
Litteratur
- A.T. Balaban. En trivalent graf over pige ti // J. Combin. Teori Ser. F. - 1972. - Udgave. 12 . - S. 1-5 .
- T. Pisanski, M. Boben, D. Marusic, A. Orbanic. De generaliserede Balaban-konfigurationer // Preprint. – 2001.
- M. O'Keefe, PK Wong. En mindste graf over pige 10 og valens 3 // J. Combin. Teori Ser. B. - 1980. - Udgave. 29 .
- JA Bondy, USR Murty. Grafteori med applikationer . - New York: Nordholland, 1976. - s . 237 .