About: Meredith graph     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatRegularGraphs, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/c/43WBSHsfAf

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.

AttributesValues
rdf:type
rdfs:label
  • Graphe de Meredith (fr)
  • Meredith graph (en)
  • Граф Мередита (ru)
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)
name
  • Meredith graph (en)
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/Meredith_graph.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Meredith_graph_3COL.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Meredith_graph_5color_edge.svg
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
thumbnail
namesake
  • G. H. Meredith (en)
automorphisms
chromatic index
chromatic number
diameter
edges
girth
image caption
  • The Meredith graph (en)
properties
radius
vertices
has 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)
book thickness
queue number
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git147 as of Sep 06 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 53 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software