Meredith graph (original) (raw)
Le graphe de Meredith est, en théorie des graphes, un graphe 4-régulier possédant 70 sommets et 140 arêtes.
| Property | Value |
|---|---|
| dbo:abstract | In the 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. 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. It has book thickness 3 and queue number 2. Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian. However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian. The characteristic polynomial of the Meredith graph is . (en) Le graphe de Meredith est, en théorie des graphes, un graphe 4-régulier possédant 70 sommets et 140 arêtes. (fr) Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году. Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтонов. Граф имеет книжную толщину 3 и число очередей 2. Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтонов. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновы. Характеристический многочлен графа Мередита равен . (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Meredith_graph.svg?width=300 |
| dbo:wikiPageID | 24128464 (xsd:integer) |
| dbo:wikiPageLength | 2219 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 852405375 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_number dbr:Regular_graph dbr:Characteristic_polynomial dbr:Undirected_graph dbc:Individual_graphs dbc:Regular_graphs dbr:Crispin_Nash-Williams dbr:Mathematics dbr:Chromatic_number dbr:W._T._Tutte dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Graph_theory dbr:Hamiltonian_graph dbr:Planar_graph dbr:Chromatic_index dbr:Book_thickness dbr:Eulerian_graph dbr:File:Meredith_graph.svg |
| dbp:automorphisms | 38698352640 (xsd:decimal) |
| dbp:bookThickness | 3 (xsd:integer) |
| dbp:chromaticIndex | 5 (xsd:integer) |
| dbp:chromaticNumber | 3 (xsd:integer) |
| dbp:diameter | 8 (xsd:integer) |
| dbp:edges | 140 (xsd:integer) |
| dbp:girth | 4 (xsd:integer) |
| dbp:imageCaption | The Meredith graph (en) |
| dbp:name | Meredith graph (en) |
| dbp:namesake | G. H. Meredith (en) |
| dbp:properties | dbr:Eulerian_graph |
| dbp:queueNumber | 2 (xsd:integer) |
| dbp:radius | 7 (xsd:integer) |
| dbp:vertices | 70 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Infobox_graph dbt:Reflist |
| dct:subject | dbc:Individual_graphs dbc:Regular_graphs |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatIndividualGraphs yago:VisualCommunication106873252 yago:WikicatRegularGraphs |
| rdfs:comment | Le graphe de Meredith est, en théorie des graphes, un graphe 4-régulier possédant 70 sommets et 140 arêtes. (fr) In the 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. 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. It has book thickness 3 and queue number 2. Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian. However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian. (en) Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году. Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтонов. Граф имеет книжную толщину 3 и число очередей 2. Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтонов. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновы. . (ru) |
| rdfs:label | Graphe de Meredith (fr) Meredith graph (en) Граф Мередита (ru) |
| owl:sameAs | freebase:Meredith graph yago-res:Meredith graph wikidata:Meredith graph dbpedia-fr:Meredith graph dbpedia-ru:Meredith graph https://global.dbpedia.org/id/2tXwB |
| prov:wasDerivedFrom | wikipedia-en:Meredith_graph?oldid=852405375&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Meredith_graph.svg wiki-commons:Special:FilePath/Meredith_graph_3COL.svg wiki-commons:Special:FilePath/Meredith_graph_5color_edge.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Meredith_graph |
| is dbo:wikiPageWikiLink of | dbr:List_of_graphs_by_edges_and_vertices dbr:Gallery_of_named_graphs dbr:Quartic_graph |
| is foaf:primaryTopic of | wikipedia-en:Meredith_graph |
