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..
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..
A snark is a connected bridgeless cubic graph (i.e., a biconnected cubic graph) with edge chromatic number of four. (By Vizing's theorem, the edge chromatic number of every cubic graph is either three or four, so a snark corresponds to the special case of four.) Snarks are therefore class 2 graphs.In order to avoid trivial cases, snarks are commonly restricted to be connected (so that the graph union of two Petersen graphs is excluded), have girth 5 or more and not to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial (Read and Wilson 1998, p. 263).Snarks that are trivial in the above senses are sometimes called "reducible" snarks. A number of reducible snarks are illustrated above.The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graph graph minors. This conjecture was proven in 2001 by Robertson, Sanders, Seymour, and Thomas,..
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 -hypercube graph, also called the -cube graph and commonly denoted or , is the graph whose vertices are the symbols , ..., where or 1 and two vertices are adjacent iff the symbols differ in exactly one coordinate.The graph of the -hypercube is given by the graph Cartesian product of path graphs . The -hypercube graph is also isomorphic to the Hasse diagram for the Boolean algebra on elements.The above figures show orthographic projections of some small -hypercube graphs using the first two of each vertex's set of coordinates. Note that above is a projection of the usual cube looking along a space diagonal so that the top and bottom vertices coincide, and hence only seven of the cube's eight vertices are visible. In addition, three of the central edges connect to the upper vertex, while the other three connect to the lower vertex.Hypercube graphs may be computed in the Wolfram Language using the command HypercubeGraph[n], and precomputed properties..
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 Meredith graph is a quartic graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4-regular 4-connected graph is Hamiltonian.It is implemented in the Wolfram Languageas GraphData["MeredithGraph"].The Meredith graph has chromatic number 3 andedge chromatic number 5.The plots above show the adjacency, incidence,and distance matrices of the graph.
The cubic graph on 12 nodes and 18 edges illustrated above in a number of embeddings. It is a snark, albeit a trivial one by the usual definition of the snark.It is implemented in the Wolfram Languageas GraphData["TietzeGraph"].Tietze's graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). In fact, it is also maximally nonhamiltonian (Clark and Entringer 1983).Tietze's graph provides a 6-color coloring of the Möbiusstrip as illustrated above.The plots above show the adjacency, incidence, and graph distance matrices for Tietze's graph.
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 Soifer graph is a planar graph on 9 nodes 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. As proved by Gethner and Springer, the Soifer graph is the smallest such counterexample (and is smaller than the Kittell graph and Errera graph).It is implemented in the Wolfram Languageas GraphData["SoiferGraph"].
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 ...
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 gear graph, also sometimes known as a bipartite wheel graph (Brandstädt et al. 1987), is a wheel graph with a graph vertex added between each pair of adjacent graph vertices of the outer cycle (Gallian 2018). The gear graph has nodes and edges.Gear graphs are unit-distance and matchstickgraphs, as illustrated in the embeddings shown above.Attractive derived unit-distance graph are produced by taking the vertex sets from the matchstick embeddings and connecting all pairs of vertices separate by a unit distance for , 6, 12, and 18, illustrated above, with the case corresponding to the wheel graph .Ma and Feng (1984) proved that all gear graphs are graceful, and Liu (1996) showed that if two or more vertices are inserted between every pair of vertices of the outer cycle of the wheel, the resulting graph is also graceful (Gallian 2018).Precomputed properties of gear graphs are given in the Wolfram Language by GraphData["Gear",..
"The" octahedral graph is the 6-node 12-edge Platonic graph having the connectivity of the octahedron. It is isomorphic to the circulant graph , the cocktail party graph , the complete tripartite graph , and the 4-dipyramidal graph. Several embeddings of this graph are illustrated above.It is implemented in the Wolfram Languageas GraphData["OctahedralGraph"].The octahedral graph has 6 nodes, 12 edges, vertex connectivity 4, edge connectivity 4, graph diameter 2, graph radius 2, and girth 3. It is the unique 6-node quartic graph, and is also a quartic symmetric graph. It has chromatic polynomialand chromatic number 3. It is an integral graph with graph spectrum . Its automorphism group is of order .The octahedral graph is the line graph of the tetrahedralgraph.There are three minimal integral drawings of the octahedral graph, illustrated above, all with maximum edge length of 7 (Harborth and Möller 1994).The..
"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 cubical graph is the Platonic graph corresponding to the connectivity of the cube. It is isomorphic to the generalized Petersen graph , bipartite Kneser graph , 4-crossed prism graph, crown graph , grid graph , hypercube graph , and prism graph . It is illustrated above in a number of embeddings (e.g., Knuth 2008, p. 14).It has 12 distinct (directed) Hamiltonian cycles, corresponding to the unique order-4 LCF notation .It is a unit-distance graph, as shown above in a unit-distance drawing (Harborth and Möller 1994).The minimal planar integral drawings of the cubical graph, illustrated above, has maximum edge length of 2 (Harborth et al. 1987). They are also graceful (Gardner 1983, pp. 158 and 163-164). can be constructed as the graph expansion of with steps 1 and 1, where is a path graph. Excising an edge of the cubical graph gives the prism graph .The cubical graph has 8 nodes, 12 edges, vertex connectivity 3, edge connectivity..
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..
Connecting the centers of touching spheres in a three-dimensional Apollonian gasket by edges given a graph known as the Apollonian network. This process is illustrated above for the case of the planar Apollonian gasket. This network turns out to have some very special properties. In addition to being either deterministic or random, they are simultaneously scale-free, display small-world effects, can be embedded in an Euclidean lattice, and show space filling as well as matching graph properties. These networks describe force chains in granular packings, fragmented porous media, hierarchical road systems, and area-covering electrical supply networks (Andrade et al. 2005). Apollonian networks share many features of neuronal systems, and have been used to study the brain (Pellegrini et al. 2007).The first few two-dimensional Apollonian networks are illustrated above. The order-twonetwork has the connectivity of the Fano plane.Apollonian..
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..
In graph theory, a cycle graph , sometimes simply known as an -cycle (Pemmaraju and Skiena 2003, p. 248), is a graph on nodes containing a single cycle through all nodes. A different sort of cycle graph, here termed a group cycle graph, is a graph which shows cycles of a group as well as the connectivity between the group cycles. Cycle graphs can be generated in the Wolfram Language using CycleGraph[n]. Precomputed properties are available using GraphData["Cycle", n]. A graph may be tested to see if it is a cycle graph using PathGraphQ[g] && Not[AcyclicGraphQ[g]], where the second check is needed since the Wolfram Language believes cycle graphs are also path graphs (a convention which seems nonstandard at best).Special cases include (the triangle graph), (the square graph, also isomorphic to the grid graph ), (isomorphic to the bipartite Kneser graph ), and (isomorphic to the 2-Hadamard graph). The -cycle graph is isomorphic..
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 Petersen graph is the cubic graph on 10 vertices and 15 edges which is the unique -cage graph (Harary 1994, p. 175), as well as the unique -Moore graph. It can be constructed as the graph expansion of with steps 1 and 2, where is a path graph (Biggs 1993, p. 119). Excising an edge of the Petersen graph gives the 4-Möbius ladder . It is illustrated above in several embeddings (D'Angelo and Saaty and Kainen 1986; Harary 1994, p. 89; West 2000, p. 229; Knuth 2008, p. 39).The Petersen graph can be generalized, with the resulting graphs being known as generalized Petersen graphs for and . The Petersen graph corresponds to .The Petersen graph has girth 5, diameter 2, edge chromatic number 4, chromatic number 3, and chromatic polynomialThe Petersen graph is a cubic symmetric graph and is nonplanar. The following elegant proof due to D. West demonstrates that the Petersen graph is nonhamiltonian. If there is a..