Herschel graph

English right|thumb|The Herschel graph Etymology From en Herschel a surname + en graph, after British astronomer Alexander Stewart Herschel (1836–1907), who identified the associated polyhedron (an enneahedron) as one for which there is no solution to the icosian game. Pronunciation en æf 3 Proper noun en mathematics graph theory A bipartite undirected graph with 11 vertices and 18 edges that is the smallest non-Hamiltonian polyhedral graph. en 1994 Ralph P. Grimaldi Discrete and Combinatorial Mathematics: An Applied Introduction 587 https://books.google.com.au/books?id=JfUYAQAAIAAJ&q=%22Herschel+graph%22%7C%22Herschel+graphs%22&dq=%22Herschel+graph%22%7C%22Herschel+graphs%22&hl=en&sa=X&ved=0ahUKEwj4nuvn-JrPAhXn1IMKHQmJDJ4Q6AEI_QEwJg Select a suitable independent set / and use part (b) to show that the graph in Fig. 11.81 (known as the Herschel graph) has no Hamilton cycle. en 2004 William Kocay; Donald L. Kreher Graphs, Algorithms, and Optimization https://books.google.com.au/books?id=zxSmHAoMiRUC&pg=PA202&dq=%22Herschel+graph%22%7C%22Herschel+graphs%22&hl=en&sa=X&ved=0ahUKEwj4nuvn-JrPAhXn1IMKHQmJDJ4Q6AEIxQEwGw#v=onepage&q=%22Herschel%20graph%22%7C%22Herschel%20graphs%22&f=false 202 A bipartite graph like the Herschel graph of Figure 9.2 is also non-hamiltonian, but the algorithm is not likely to delete enough vertices to notice that it has a large separating set. 2006, Michael S. Keane, Dee Denteneer, Frank Hollander, Evgeny Verbitskiy, Dynamics and Stochastics, Institute of Mathematical Statistics, Lecture Notes—Monograph Series, Volume 48, page 174, It is difficult to control what loops may arise: for example the Herschel graph [3] shows that a convex polyhedron need not be Hamiltonian as a graph. Synonyms smallest non-Hamiltonian polyhedral graph Herschel's graph See also icosian game en eponyms