Jarl af Meredith
| Jarl af Meredith | |
|---|---|
| Opkaldt efter | Guy Meredith |
| Toppe | 70 |
| ribben | 140 |
| Diameter | otte |
| Omkreds | 5 |
| Automorfismer | 38698352640 |
| Kromatisk tal | 3 |
| Kromatisk indeks | 5 |
| Ejendomme | Euler |
| bogtykkelse | 3 |
| Antal køer | 2 |
| Mediefiler på Wikimedia Commons | |
Meredith-grafen er en 4-regulær urettet graf med 70 hjørner og 140 kanter, opdaget af Guy Meredith i 1973 [1] .
Meredith-grafen er 4-kant-forbundet og 4-kant-forbundet . Den har et kromatisk tal på 3, et kromatisk indeks på 5, en radius på 7, en diameter på 8, en omkreds på 4 og er ikke Hamiltonsk [2] . Grafen har bogtykkelse 3 og antal køer 2 [3] .
Grafen blev udgivet i 1973 og gav et modeksempel til Crispin Nash-Williams' formodning om, at enhver 4-regulær vertex-4-forbundet graf altid er Hamiltonsk [4] [5] . Tatt viste dog, at alle 4-forbundne plane grafer er Hamiltonske [6] .
Meredith-grafens karakteristiske polynomium er
.
Galleri
-
Jarlen af Merediths kromatiske tal er 3.
-
Det kromatiske indeks for jarlen af Meredith er 5.
Noter
- ↑ Weisstein, Eric W. Meredith graf på Wolfram MathWorld- webstedet .
- ↑ Bondy JA, Murty USR Graph Theory. - Springer, 2007. - S. 470.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT . Kandidatafhandling, Tübingen Universitet, 2018
- ↑ Meredith GHJ Regular 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs // J. Combin. Th.. - 1973. - Udgave. B 14 . - S. 55-60 .
- ↑ Bondy JA, Murty USR Grafteori med applikationer. - New York: Nordholland, 1976. - S. 239.
- ↑ Recent Progress in Combinatorics / Tutte W. Literature T .. - New York: Academic Press, 1969.
Links
- AE Brouwers hjemmeside: Armanios-Wells grafen Arkiveret 14. april 2018 på Wayback Machine