The king graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a king.The number of edges in the king graph is , so for , 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).The order graph has chromatic number for and for . For , 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....King graphs are implemented in the Wolfram Language as GraphData["King", m, n].All king graphs are Hamiltonian and biconnected. The only regular king graph is the -king graph, which is isomorphic to the tetrahedral graph . The -king graphs are planar only for (with the case corresponding to path graphs) and , some embeddings of which are illustrated above.The -king graph is perfect iff (S. Wagon, pers. comm., Feb. 22, 2013).Closed formulas for the numbers of -cycles of with are given by(1)(2)(3)(4)where the formula for appears in Perepechko and Voropaev.The..
A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on , 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph is conventionally considered traceable. The first few are illustrated above, with a Hamiltonian path indicated in orange for each.Every self-complementary graph is traceable(Clapham 1974; Camion 1975; Farrugia 1999, p. 52).The following table lists some named graphs that are traceable but not Hamiltonian.graph theta-0 graph7Petersen graph10Herschel graph11Blanuša snarks18flower snark20Coxeter graph28double star snark30Tutte's graph46Szekeres snark50McLaughlin graph276
A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.A Hamiltonian graph on nodes has graph circumference .While it would be easy to make a general definition of "Hamiltonian" that goes either way as far as the singleton graph is concerned, defining "Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles" to be a subset of "cycles" in general would lead to the convention that the singleton graph is nonhamiltonian (B. McKay, pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22, 2007). The convention in this work and in GraphData is that is Hamiltonian, while is nonhamiltonian.The numbers of simple Hamiltonian graphs on nodes for , 2, ... are..
The queen graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a queen. The -queen graphs have nice embeddings, illustrated above. In general, the default embedding with vertices corresponding to squares of the chessboard has degenerate superposed edges, the only nontrivial exception being the -queen graph.Queen graphs are implemented in the Wolfram Language as GraphData["Queen", m, n].The following table summarized some special cases of queen graphs.namecomplete graph tetrahedral graph The following table summarizes some named graph complements of queen graphs.-queen graph-knight graph-queen graph-queen graph-knight graphAll queen graphs are Hamiltonian and biconnected. The only planar and only regular queen graph is the -queen graph, which is isomorphic to the tetrahedral graph .The only perfect queen graphs are , , and .A closed formula..
The pentatope is the simplest regular figure in four dimensions, representing the four-dimensional analog of the solid tetrahedron. It is also called the 5-cell, since it consists of five vertices, or pentachoron. The pentatope is the four-dimensional simplex, and can be viewed as a regular tetrahedron in which a point along the fourth dimension through the center of is chosen so that . The pentatope has Schläfli symbol .It is one of the six regular polychora.The skeleton of the pentatope is isomorphic to the complete graph , known as the pentatope graph.The pentatope is self-dual, has five three-dimensional facets (each the shape of a tetrahedron), 10 ridges (faces), 10 edges, and five vertices. In the above figure, the pentatope is shown projected onto one of the four mutually perpendicular three-spaces within the four-space obtained by dropping one of the four vertex components (R. Towle)...
The Harborth graph is the smallest known 4-regular matchstick graph. It is therefore both planar and unit-distance. It has 104 edges and 52 vertices. This graph was named after its discoverer H. Harborth, who first presented it to a general public in 1986 (Harborth 1994, Petersen 1996, Gerbracht 2006).The Harborth graph is implemented in the WolframLanguage as GraphData["HarborthGraph"].Analytic expressions for the vertices consisting of algebraic numbers of degree 22 (with large coefficients) were derived by Gerbracht (2006). As a consequence, Gerbracht (2006) also proved that the Harborth graph is rigid.
The torus grid graph is the graph formed from the graph Cartesian product of the cycle graphs and . is isomorphic to . can be formed starting with an grid graph and connecting corresponding left/right and top/bottom vertex pairs with edges. While such an embedding has overlapping edges in the plane, it can naturally be placed on the surface of a torus with no edge intersections or overlaps. Torus grid graphs are therefore toroidal graphs. The isomorphic torus grid graphs and are illustrated above.The torus grid graphs are quartic and Hamiltonianand have vertex count(1)Torus grid graphs are circulant graphs iff and are relatively prime, i.e., . In such cases, is isomorphic to . Special cases are summarized in the following table and illustrated above in attractive (but non-toroidal) embddings.graphcirculant graph generalized quadrangle quartic vertex-transitive graph Qt65tesseract graph Harary et al. (1973) conjectured that(2)for all..
The Desargues graph is the cubic symmetric graph on 20 vertices and 30 edges illustrated above in several embeddings. It is isomorphic to the generalized Petersen graph and to the bipartite Kneser graph . It is the incidence graph of the Desargues configuration. It can be represented in LCF notation as (Frucht 1976). It can also be constructed as the graph expansion of with steps 1 and 3, where is a path graph. It is distance-transitive and distance-regular graph and has intersection array .The Desargues graph is one of three cubic graphs on 20 nodes with smallest possible graph crossing number of 6 (the others being two unnamed graphs denoted CNG 6B and CNG 6C by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Desargues is an integral graph with graph spectrum . It is cospectral with another nonisomorphic graph (Haemers and Spence 1995, van Dam and Haemers 2003).It is also a unit-distance..
The Shrikhande graph is a strongly regular graph on 16 nodes. It is cospectral with the rook graph , so neither of the two is determined by spectrum.The Shrikhande graph is the smallest distance-regular graph that is not distance-transitive (Brouwer et al. 1989, p. 136). It has intersection array .The Shrikhande graph is implemented in the WolframLanguage as GraphData["ShrikhandeGraph"].The Shrikhande graph has two generalized LCF notations of order 8, eleven of order 4, 53 of order 2, and 2900 of order 1. The graphs with LCF notations of orders four and eight are illustrated above.The Shrikhande graph appears on the cover of the book Combinatorial Matrix Theoryby Brualdi and Ryser (1991); illustrated above.The plots above show the adjacency, incidence, and graph distance matrices for the Shrikhande graph.It is an integral graph with graph spectrum .The bipartite double graph of the Shrikhandegraph is the Kummer graph.The..
The disdyakis dodecahedron is the dual polyhedron of the Archimedean great rhombicuboctahedron and Wenninger dual . It is also called the hexakis octahedron (Unkelbach 1940; Holden 1971, p. 55).If the original great rhombicuboctahedronhas unit side lengths, then the resulting dual has edge lengths(1)(2)(3)The inradius is(4)Scaling the disdyakis dodecahedron so that gives a solid with surface area and volume(5)(6)
The cocktail party graph of order , also called the hyperoctahedral graph (Biggs 1993, p. 17) or Roberts graph, is the graph consisting of two rows of paired nodes in which all nodes but the paired ones are connected with a graph edge. It is the graph complement of the ladder rung graph , and the dual graph of the hypercube graph . It is the skeleton of the -cross polytope.This graph arises in the handshake problem. It is a complete n-partite graph that is denoted by Brouwer et al. (1989, pp. 222-223), and is distance-transitive, and hence also distance-regular.The cocktail party graph of order is isomorphic to the circulant graph . The -cocktail party graph is also the -Turán graph.Special cases are summarized in the following table.-cocktail party graph1empty graph 2square graph 3octahedral graph416-cell graphThe -cocktail party graph has independence polynomialwith corresponding recurrence equation..
The Heawood graph is a cubic graph on 14 vertices and 21 edges which is the unique (3,6)-cage graph. It is also a Moore graph. The Heawood graph is also the generalized hexagon , and its line graph is the generalized hexagon . The Heawood graph is illustrated above in a number of embeddings.It has graph diameter 3, graph radius 3, and girth 6. It is cubic symmetric, nonplanar, Hamiltonian, and can be represented in LCF notation as .It has chromatic number 2 and chromaticpolynomialIts graph spectrum is .It is 4-transitive, but not 5-transitive (Harary 1994, p. 173).The Heawood graph is one of eight cubic graphs on 14 nodes with smallest possible graph crossing number of 3 (another being the generalized Petersen graph ), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Heawood graph corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line incidence..
The Franklin graph is the 12-vertex cubic graph shown above whose embedding on the Klein bottle divides it into regions having a minimal coloring using six colors, thus providing the sole counterexample to the Heawood conjecture. The graph is implemented in the Wolfram Language as GraphData["FranklinGraph"].It is the 6-crossed prism graph.The minimal coloring of the Franklin graph is illustrated above.The Franklin graph is nonplanar but Hamiltonian. It has LCF notations and .The graph spectrum of the Franklin graph is .
The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails.It is also an identity graph.The Fritsch graph and Soifergraph provide smaller (and in fact the smallest possible) counterexamples.
The Royle graphs are the two unique simple graphs on eight nodes whose sigma polynomials have nonreal roots (Read and Wilson 1998, p. 265). The sigma polynomials of these graphs are given by(1)(2)respectively, each of which has two nonreal roots (and where the members of each pairs are complex conjugates of each other).The Royle graphs are implemented in the Wolfram Language as GraphData["RoyleGraph1"] and GraphData["RoyleGraph2"].The numbers of simple graphs having this property on , 2, ... vertices are 0, 0, 0, 0, 0, 0, 0, 2, 42, ..., with the 42 such graphs on 9 vertices illustrated above.
Grünbaum conjectured that for every , , there exists an -regular, -chromatic graph of girth at least . This result is trivial for or , but only a small number of other such graphs are known, including the 12-node Chvátal graph, 21-node Brinkmann graph, and 25-node Grünbaum graph. The Chvátal graph is illustrated above in a couple embeddings (e.g., Bondy; Knuth 2008, p. 39).It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized LCF notation of order 4 (illustrated above), two of order 6 (illustrated above), and 43 of order 1.The Chvátal graph is implemented in the WolframLanguage as GraphData["ChvatalGraph"].The Chvátal graph is a quartic graph on 12 nodes and 24 edges. It has chromatic number 4, and girth 4. The Chvátal graph has graph spectrum ...
Grünbaum conjectured that for every , , there exists an -regular, -chromatic graph of girth at least . This result is trivial for and , but only a small number of other such graphs are known, including the Grünbaum graph, illustrated above, Brinkmann graph, and Chvátal graph.The Grünbaum graph can be constructed from the dodecahedral graph by adding an additional ring of five vertices around the perimeter and cyclically connecting each new vertex to three others as shown above (left figure). A more symmetrical embedding is shown in the center figure above, and an LCF notation-based embedding is shown in the right figure. This graph is implemented in the Wolfram Language as GraphData["GruenbaumGraph25"].The Grünbaum graph has 25 vertices and 50 edges. It is a quartic graph with chromatic number 4, and therefore has . It has girth .It has diameter 4, graph radius 3, edge connectivity 4, and vertex connectivity..
The Moser spindle is the 7-node unit-distance graph illustrated above (Read and Wilson 1998, p. 187). It is sometimes called the Hajós graph (e.g., Bondy and Murty 2008. p. 358), though this term is perhaps more commonly applied to the Sierpiński sieve graph .It is implemented in the Wolfram Languageas GraphData["MoserSpindle"].A few other (non-unit) embeddings of the Moser spindle are illustrated above.The Moser spindle has chromatic number 4 (as does the Golomb graph), meaning the chromatic number of the plane must be at least four, thus establishing a lower bound on the Hadwiger-Nelson problem. After a more than 50-year gap, the first unit-distance graph raising this bound (the de Grey graph with chromatic number 5) was constructed by de Grey (2018).
The (connected) caveman graph is a graph arising in social network theory formed by modifying a set of isolated -cliques (or "caves") by removing one edge from each clique and using it to connect to a neighboring clique along a central cycle such that all cliques form a single unbroken loop (Watts 1999). A number of cavemen graphs formed in this manner from are illustrated above.Caveman graphs are perfect.Caveman graphs will are implemented in the Wolfram Language as GraphData["Caveman", n, k].
"The" tetrahedral graph is the Platonic graph that is the unique polyhedral graph on four nodes which is also the complete graph and therefore also the wheel graph . It is implemented in the Wolfram Language as GraphData["TetrahedralGraph"].The tetrahedral graph has a single minimal integral drawing, illustrated above (Harborth and Möller 1994), with maximum edge length 4.The minimal planar integral drawing of the tetrahedral graph, illustrated above, has maximum edge length of 17 (Harborth et al. 1987). The tetrahedral graph is also graceful (Gardner 1983, pp. 158 and 163-164).The tetrahedral graph has 4 nodes, 6 edges, vertex connectivity 4, edge connectivity 3, graph diameter 1, graph radius 1, and girth 3. It has chromatic polynomial(1)(2)and chromatic number 4. It is planarand cubic symmetric.The tetrahedral graph is an integral graph with graph spectrum . Its automorphism group has order .The..
The dodecahedral graph is the Platonic graph corresponding to the connectivity of the vertices of a dodecahedron, illustrated above in four embeddings. The left embedding shows a stereographic projection of the dodecahedron, the second an orthographic projection, the third is from Read and Wilson (1998, p. 162), and the fourth is derived from LCF notation.It is the cubic symmetric denoted and is isomorphic to the generalized Petersen graph . It can be described in LCF notation as [10, 7, 4, , , 10, , 7, , .It is distance-regular with intersection array and is also distance-transitive.It is also a unit-distance graph (Gerbracht2008), as shown above in a unit-distance drawing.Finding a Hamiltonian cycle on this graph is known as the icosian game. The dodecahedral graph is not Hamilton-connected and is the only known example of a vertex-transitive Hamiltonian graph (other than cycle graphs ) that is not H-*-connected (Stan Wagon, pers...
A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order is a simple graph obtained by introducing a twist in a prism graph of order that is isomorphic to the circulant graph . Möbius ladders are sometimes denoted .The 4-Möbius ladder is known as the Wagner graph. The -Möbius ladder rung graph is isomorphic to the Haar graph .Möbius ladders are Hamiltonian. They are also graceful(Gallian 1987, Gallian 2018).The numbers of directed Hamiltonian cycles for , 4, ... are 12, 10, 16, 14, 20, 18, 24, ... (OEIS A124356), given by the closed form(1)The -Möbius ladder graph has independence polynomial(2)Recurrence equations for the independence polynomial and matching polynomial are given by(3)(4)The bipartite double graph of the -Möbius ladder is the prism graph ...
The -ladder graph can be defined as , where is a path graph (Hosoya and Harary 1993; Noy and Ribó 2004, Fig. 1). It is therefore equivalent to the grid graph. The ladder graph is named for its resemblance to a ladder consisting of two rails and rungs between them (though starting immediately at the bottom and finishing at the top with no offset).Hosoya and Harary (1993) also use the term "ladder graph" for the graph Cartesian product , where is the complete graph on two nodes and is the cycle graph on nodes. This class of graph is however more commonly known as a prism graph.Ball and Coxeter (1987, pp. 277-278) use the term "ladder graph" to refer to the graph known in this work as the ladder rung graph.The ladder graph is graceful (Maheo 1980).The chromatic polynomial, independence polynomial, and reliability polynomial of the ladder graph are given by(1)(2)(3)where . Recurrence equations for the chromatic..
The icosahedral graph is the Platonic graph whose nodes have the connectivity of the icosahedron, illustrated above in a number of embeddings. The icosahedral graph has 12 vertices and 30 edges.Since the icosahedral graph is regular and Hamiltonian, it has a generalized LCF notation. In fact, there are two distinct generalized LCF notations of order 6-- and --8 of order 2, and 17 of order 1, illustrated above.It is implemented in the Wolfram Languageas GraphData["IcosahedralGraph"].It is a distance-regular graph with intersection array , and therefore also a Taylor graph. It is also distance-transitive.There are two minimal integral drawings of the icosahedral graph, illustrated above, all with maximum edge length of 8 (Harborth and Möller 1994). It is also graceful (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35), with five fundamentally different labelings (Gardner 1983, p. 164).The..
The rook graph (confusingly called the grid by Brouwer et al. 1989, p. 440) and also sometimes known as a lattice graph (e.g., Bouwer) is the graph Cartesian product of complete graphs, which is equivalent to the line graph of the complete bipartite graph . This is the definition adopted for example by Brualdi and Ryser (1991, p. 153), although restricted to the case . This definition corresponds to the connectivity graph of a rook chess piece (which can move any number of spaces in a straight line-either horizontally or vertically, but not diagonally) on an chessboard.The graph has vertices and edges. It is regular of degree , has diameter 3, girth 3 (for ), and chromatic number . It is also perfect (since it is the line graph of a bipartite graph) and vertex-transitive.The rook graph is also isomorphic to the Latin square graph. The vertices of such a graph are defined as the elements of a Latin square of order , with two vertices being adjacent..
A complete graph is a graph in which each pair of graph vertices is connected by an edge. The complete graph with graph vertices is denoted and has (the triangular numbers) undirected edges, where is a binomial coefficient. In older literature, complete graphs are sometimes called universal graphs.The complete graph is also the complete n-partite graph .The complete graph on nodes is implemented in the Wolfram Language as CompleteGraph[n]. Precomputed properties are available using GraphData["Complete", n]. A graph may be tested to see if it is complete in the Wolfram Language using the function CompleteGraphQ[g].The complete graph on 0 nodes is a trivial graph known as the null graph, while the complete graph on 1 node is a trivial graph known as the singleton graph.In the 1890s, Walecki showed that complete graphs admit a Hamilton decomposition for odd , and decompositions into Hamiltonian cycles plus a perfect matching for..
A circulant graph is a graph of graph vertices in which the th graph vertex is adjacent to the th and th graph vertices for each in a list . The circulant graph gives the complete graph and the graph gives the cyclic graph .The circulant graph on vertices on an offset list is implemented in the Wolfram Language as CirculantGraph[n, l]. Precomputed properties are available using GraphData["Circulant", n, l].With the exception of the degenerate case of the path graph , connected circulant graphs are biconnected, bridgeless, cyclic, Hamiltonian, LCF, regular, traceable, and vertex-transitive.A graph is a circulant iff the automorphism group of contains at least one permutation consisting of a minimal cycle of length .The numbers of circulant graphs on , 2, ... nodes (counting empty graphs as circulant graphs) are 1, 2, 2, 4, 3, 8, 4, 12, ... (OEIS A049287), the first few of which are illustrated above. Note that these numbers cannot be counted..
"The" Sylvester graph is a quintic graph on 36 nodes and 90 edges that is the unique distance-regular graph with intersection array (Brouwer et al. 1989, §13.1.2; Brouwer and Haemers 1993). It is a subgraph of the Hoffman-Singleton graph obtainable by choosing any edge, then deleting the 14 vertices within distance 2 of that edge.It has graph diameter 3, girth 5, graph radius 3, is Hamiltonian, and nonplanar. It has chromatic number 4, edge connectivity 5, vertex connectivity 5, and edge chromatic number 5.It is an integral graph and has graph spectrum (Brouwer and Haemers 1993).The Sylvester graph of a configuration is the set of ordinarypoints and ordinary lines.