Hrabě Harris-Wong
| hrabě Harris-Wong | |
|---|---|
| Vrcholy | 70 |
| žebra | 105 |
| Poloměr | 6 |
| Průměr | 6 |
| obvod | deset |
| Automorfismy | 24 ( S4 ) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Vlastnosti |
kubická buňka bez hamiltonských trojúhelníků |
V teorii grafů je Harris-Wongův graf 3-pravidelný neorientovaný graf se 70 vrcholy a 105 hranami [1] .
Barevné číslo grafu je 2, chromatický index je 3, průměr a poloměr grafu jsou 6 a obvod je 10.
Graf je hamiltonovský , 3-vrcholově spojený , 3-hranně spojený , rovinný kubický graf.
Charakteristickým polynomem Harris-Wongova grafu je
Historie
V roce 1972 AT Balaban publikoval (3-10) -buňkový kubický graf, který má minimální počet vrcholů pro obvod 10 [2] . Jednalo se o první otevřenou (3-10)-buňku, ale není unikátní [3] .
Úplný seznam (3-10)-buněk a důkaz minimality byl dán O'Keefe a Wong v roce 1980 [4] . Existují pouze tři odlišné (3-10)-buňky - Balabanův 10-buňkový , Harrisův graf a Harris-Wongův graf [5] . Navíc Harris-Wongův graf a Harrisův graf jsou kospektrální grafy .
Galerie
-
Barevné číslo hraběte Harris-Wonga je 2.
-
Chromatický index Harris-Wongova grafu je 3.
-
Alternativní kresba hraběte Harris-Wonga.
-
8 obletů hraběte Harrise - Wonga.
Poznámky
- ↑ Weisstein, Eric W. Harries–Wong Graph na webu Wolfram MathWorld .
- ↑ Balaban, 1972 , str. 1-5.
- ↑ Pisanski, Boben, Marusic, Orbanic, 2001 .
- ↑ O'Keefe, Wong, 1980 , str. 91-105.
- ↑ Bondy, Murty, 1976 , str. 237.
Literatura
- A. T. Balaban. Trivalentní graf dívky deset // J. Combin. Teorie Ser. B. - 1972. - Vydání. 12 . - S. 1-5 .
- T. Pisanski, M. Boben, D. Marusic, A. Orbanic. Generalized Balaban Configurations // Preprint. — 2001.
- M. O'Keefe, PK Wong. Nejmenší graf dívky 10 a valence 3 // J. Combin. Teorie Ser. B. - 1980. - Vydání. 29 .
- JA Bondy, USR Murty. Teorie grafů s aplikacemi . - New York: Severní Holandsko, 1976. - s . 237 .