Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette's conditions is the cubical graph, which is indeed Hamiltonian. The skeletons of the truncated octahedron, great rhombicuboctahedron, and great rhombicosidodecahedron also satisfy the conditions and, since they are Archimedean solids, are indeed Hamiltonian. Holton et al. (1985) proved that all graphs having fewer than 66 vertices satisfy the conjecture, but the general conjecture remains open.Similarly, Barnette conjectured that all cubic, 3-connected, planar graphs with a face size of at most 6 are Hamiltonian. Aldred et al. (2000) have verified this conjecture for all graphs with fewer than 177 vertices.
The singleton graph is the graph consisting of a single isolated node with no edges. It is therefore the empty graph on one node. It is commonly denoted (i.e., the complete graph on one node).By convention, the singleton graph is considered to be Hamiltonian(B. McKay, pers. comm., Mar. 22, 2007).
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)...
A -regular simple graph on nodes is strongly -regular if there exist positive integers , , and such that every vertex has neighbors (i.e., the graph is a regular graph), every adjacent pair of vertices has common neighbors, and every nonadjacent pair has common neighbors (West 2000, pp. 464-465). A graph that is not strongly regular is said to be weakly regular.The complete graph is strongly regular for all . The status of the trivial singleton graph is unclear. Opinions differ on if is a strongly regular graph, though since it has no well-defined parameter, it is preferable to consider it not to be strongly regular (A. E. Brouwer, pers. comm., Feb. 6, 2013).The graph complement of a non-empty non-complete strongly regular graph with parameters is another strongly regular graph with parameters .A number of strongly regular graphs are implemented in the WolframLanguage as GraphData["StronglyRegular"].The..
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.
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,..
A generalized Moore graph is a regular graph of degree where the counts of vertices at each distance , 1, ... from any vertex are 1, , , , , ..., with the last distance count not necessarily filled up. That is, all the levels are full except possibly the last which must have the rest. Alternatively, the girth is as great as the naive bound allows and the diameter is as little as the naive bound allows. Stated yet another way, a generalized Moore graph is a regular graph such that the average distance between pairs of vertices achieves the naive lower bound.The numbers of generalized Moore graphs with , 2, ... nodes are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933).The numbers of cubic generalized Moore graphs with , 4, 6, ... nodes are 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007).It is an open problem if there are infinitely many generalized Moore graphs of each degree...
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 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 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 flower snarks are a family of snarks discovered by Isaacs (1975) and denoted . is Tietze's graph, which is a "reducible snark" since it contains a cycle of length less than 5. is illustrated above in two embeddings, the second of which appears in Scheinerman and Ullman (2011, p. 96) as an example of a graph with edge chromatic number and fractional edge chromatic number (4 and 3, respectively) both integers but not equal. is maximally nonhamiltonian for odd (Clark and Entringer 1983).
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 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..
A bicubic graph is a bipartite cubicgraph.Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture), but a number of nonhamiltonian bicubic graphs have subsequently been discovered.The numbers of simple bicubic graphs on , 4, ... nodes are 0, 0, 1, 1, 2, 5, 13, 38, 149, ... (OEIS A006823), the first few of which are illustrated above.The following table summarizes some named bicubic graphs.graph utility graph6cubical graph8Franklin graph12Heawood graph14Möbius-Kantor graph16Pappus graph18Desargues graph20truncated octahedral graph24Levi graph30Dyck graph32great rhombicuboctahedral graph48Gray graph54Balaban 10-cage70Foster graph90great rhombicosidodecahedral graph120Tutte 12-cage126
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 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.
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..
A cubic nonplanar graph is a graph that is both cubicand nonplanar.The following table summarizes some named nonplanar cubic graphs.graph utility graph6Petersen graph10Franklin graph12Heawood graph14Möbius-Kantor graph16first Blanusa snark18second Blanusa snark18Pappus graph18Desargues graph20flower snark20McGee graph24Coxeter graph28double star snark30Levi graph30Dyck graph32Szekeres snark50Gray graph54Balaban 10-cage70Foster graph90Biggs-Smith graph102Balaban 11-cage112Tutte 12-cage126The largest cubic nonplanar graphs having diameters 3 and 4 are illustrated above. They have 20 and 38 vertices, respectively.
A directed strongly regular graph is a simple directed graph with adjacency matrix such that the span of , the identity matrix , and the unit matrix is closed under matrix multiplication.
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 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.