Meredith graph

Meredith graph
The Meredith graph
Named after	G. H. Meredith
Vertices	70
Edges	140
Radius	7
Diameter	8
Girth	4
Chromatic number	3
Chromatic index	5
Properties	Eulerian
v · mathematical field of graph theory, the Meredith graph is a 4-regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973.[1] The Meredith graph is 4-vertex-connected and 4-edge-connected, has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is non-hamiltonian.[2] Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian.[3][4] However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.[5] The characteristic polynomial of the Meredith graph is (x − 4)(x − 1)10x21(x + 1)11(x + 3)(x2 − 13)(x6 − 26x4 + 3x3 + 169x2 − 39x − 45)4. Gallery The chromatic number of the Meredith graph is 3. The chromatic index of the Meredith graph is 5. References ^ Weisstein, Eric W., "Meredith graph" from MathWorld. ^ Bondy, J. A. and Murty, U. S. R. "Graph Theory". Springer, p. 470, 2007. ^ Meredith, G. H. J. "Regular 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs." J. Combin. Th. B 14, 55-60, 1973. ^ Bondy, J. A. and Murty, U. S. R. "Graph Theory with Applications". New York: North Holland, p. 239, 1976. ^ Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969. Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Meredith and Co. Meredith railway station Look at other dictionaries: Graphe de Meredith — Représentation du graphe de Meredith. Nombre de sommets 70 Nombre d arêtes 140 Distribution des degrés 4 régulier Rayon …   Wikipédia en Français Odd graph — The Petersen graph as an odd graph O3 Vertices Edges …   Wikipedia Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia 1957 in music — Events*January 5 Renato Carosone and his band start their American tour in Cuba. *January 6 Elvis Presley makes final appearance on the Ed Sullivan Show . *January 16 The Cavern Club opens in Liverpool, England *Paul Simon and Art Garfunkel name… …   Wikipedia Mr. Griffin Goes to Washington — Family Guy episode Peter addresses Congress Epis …   Wikipedia Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français Cary, North Carolina — Town of Cary   Town   …   Wikipedia Michael Scott (The Office) — Michael Gary Scott The Office character Steve Carell as Michael Scott First appearance Pilot Last appearance …   Wikipedia Des Moines, Iowa — Des Moines redirects here. For other uses, see Des Moines (disambiguation). City of Des Moines   City   Clockwise from top: 801 Grand …   Wikipedia Iowa — This article is about the U.S. state of Iowa. For other uses, see Iowa (disambiguation). State of Iowa …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”