Holt graph

Holt graph

Holt graph
In the Holt graph, all vertices are equivalent, and all edges are equivalent, but edges are not necessarily equivalent to their inverses.
Named after	Derek F. Holt
Vertices	27
Edges	54
Radius	3
Diameter	3
Girth	5
Automorphisms	54
Chromatic number	3
Chromatic index	5
Properties	Vertex-transitive Edge-transitive Half-transitive Hamiltonian Eulerian Cayley graph
v · mathematical field of graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric.^[1]^[2] Such graphs are not common.^[3] It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976^[4] and 1981^[5] respectively. The Holt Graph has diameter 3, radius 3 and girth 5, chromatic number 3, chromatic index 5 and is Hamiltonian with 98,472 distinct Hamiltonian cycles.^[6] It is also a 4-vertex-connected and a 4-edge-connected graph. It has an automorphism group of order 54 automorphisms.^[6] This is a smaller group than a symmetric graph with the same number of vertices and edges would have. The graph drawing on the right highlights this, in that it lacks reflectional symmetry. The characteristic polynomial of the Holt graph is $(x^3-6x+2)^6(x+2)^4(x-1)^4(x-4).\$ Gallery The chromatic number of the Holt graph is 3. The chromatic index of the Holt graph is 5. The Holt graph is Hamiltonian. References ^ Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1] ^ Alspach, Brian; Marušič, Dragan; Nowitz, Lewis (1994), "Constructing Graphs which are ½-Transitive", Journal of the Australian Mathematical Society (Series A) 56 (3): 391–402, doi:10.1017/S1446788700035564, http://anziamj.austms.org.au/JAMSA/V56/Part3/Alspach.html . ^ Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, ISBN 1584880902, p. 491. ^ Doyle, P. G. (1976), On Transitive Graphs, Senior Thesis, Harvard College . As cited by MathWorld. ^ Holt, Derek F. (1981), "A graph which is edge transitive but not arc transitive", Journal of Graph Theory 5 (2): 201–204, doi:10.1002/jgt.3190050210 . ^ ^a ^b Weisstein, Eric W., "Doyle Graph" from MathWorld. Categories: Individual graphs Regular graphs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Doyle Vaca Pseudoideal Look at other dictionaries: Universal graph — In mathematics, a universal graph is an infinite graph that contains every finite (or at most countable) graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado [cite journal author = Rado, R. title =… … Wikipedia Object-Graph Navigation Language — Object Graph Navigation Language, abgekürzt als OGNL ist eine expression language zum Lesen und Schreiben von Eigenschaften in Java Objekten. Dazu werden zum Setzen und zum Lesen des Wertes einer Eigenschaft die gleichen Ausdrücke verwendet. Zum… … Deutsch Wikipedia 54 (number) — ← 53 55 → 54 ← 50 51 52 53 54 55 56 … Wikipedia Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) … Wikipedia GXL — (Graph eXchange Language) is designed to be a standard exchange format for graphs. GXL is an XML sublanguage and the syntax is given by an XML DTD (Document Type Definition). This exchange format offers an adaptable and flexible means to support… … Wikipedia Philosophy of education — The philosophy of education is the study of the purpose, process, nature and ideals of education. This can be within the context of education as a societal institution or more broadly as the process of human existential growth, i.e. how it is… … Wikipedia Geometric group theory — is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… … Wikipedia Islam — For other uses, see Islam (disambiguation). The Kaaba, in Mecca, Saudi Arabia, is the … Wikipedia United States House of Representatives elections in New Jersey, 2010 — Elections in New Jersey Federal offices Presidential elections … Wikipedia Sri Lanka — Ceylon redirects here. For the time period of 1948 1972, see Dominion of Ceylon. For other uses, see Ceylon (disambiguation). Democratic Socialist Republic of Sri Lanka ශ්‍රී ලංකා ප්‍රජාතාන්ත්‍රික සමාජවාදී ජනරජය (Sinhala) இலங்கை சனநாயக சமத்துவ… … 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”