| dbo:abstract
|
- In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2. The first counterexample to the Tutte conjecture was the Horton graph, published by . After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by , a 78-vertex graph by , and the two Ellingham–Horton graphs. The first Ellingham–Horton graph was published by and is of order 78. At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by and is of order 54. In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices. (en)
- Графы Эллингема — Хортона — два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона. Графы названы именами Джозефа Хортона и Марка Эллингема, которые их открыли. Эти два графа дают контрпримеры гипотезе Уильяма Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым. Первым контрпримером гипотезы Татта был граф Хортона, который опубликовали Бодни и Мёрти. После графа Хортона было найдено несколько меньших контрпримеров гипотезе Татта. Среди них находятся 92-вершинный граф Хортона, 78-вершинный граф Овенса и два графа Эллингема — Хортона. Первый граф Эллингема — Хортона опубликовал Эллингем и он имеет порядок 78. В то время граф был наименьшим известным контрпримером гипотезе Татта. Второй граф Эллингема — Хортона опубликовали Эллингем и Хортон и он имеет порядок 54. В 1989 был открыт на настоящее время наименьший негамильтонов 3-связный кубический двудольный граф Жоржа, содержащий 50 вершин. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4657 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:automorphisms
|
- 16 (xsd:integer)
- 32 (xsd:integer)
|
| dbp:bookThickness
| |
| dbp:chromaticIndex
| |
| dbp:chromaticNumber
| |
| dbp:diameter
|
- 10 (xsd:integer)
- 13 (xsd:integer)
|
| dbp:edges
|
- 81 (xsd:integer)
- 117 (xsd:integer)
|
| dbp:girth
| |
| dbp:imageCaption
|
- The Ellingham–Horton 54-graph. (en)
|
| dbp:name
|
- Ellingham–Horton graphs (en)
|
| dbp:namesake
|
- Joseph Horton and Mark Ellingham (en)
|
| dbp:properties
| |
| dbp:queueNumber
| |
| dbp:radius
|
- 7 (xsd:integer)
- 9 (xsd:integer)
|
| dbp:vertices
|
- 54 (xsd:integer)
- 78 (xsd:integer)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2. (en)
- Графы Эллингема — Хортона — два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона. Графы названы именами Джозефа Хортона и Марка Эллингема, которые их открыли. Эти два графа дают контрпримеры гипотезе Уильяма Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым. (ru)
|
| rdfs:label
|
- Ellingham–Horton graph (en)
- Граф Эллингема — Хортона (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
