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 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,..
An -banana tree, as defined by Chen et al. (1997), is a graph obtained by connecting one leaf of each of copies of an -star graph with a single root vertex that is distinct from all the stars.Banana trees are graceful (Sethuraman and J. Jesintha2009, Gallian 2018).The -banana tree has rank polynomialPrecomputed properties of a number of banana trees is implemented in the Wolfram Language as GraphData["BananaTree", n, k].
A kayak paddle graph is the graph obtained by joining cycle graphs and by a path of length (Gallian 2018). is isomorphic to the 3-barbell graph.Kayak paddle graphs are planar, cactus, unit-distance and matchstick graphs. They are also bridged and traceable and have arboricity of 2.Litersky (2011) proved that kayak paddle graphs are gracefulwhen: 1. , , 2. (mod 4) for , 3. , (Litersky 2011, Gallian 2018).
An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph back to vertices of such that the resulting graph is isomorphic with . The set of automorphisms defines a permutation group known as the graph's automorphism group. For every group , there exists a graph whose automorphism group is isomorphic to (Frucht 1939; Skiena 1990, p. 185). The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties.The group of graph automorphisms of a graph may be computed in the Wolfram Language using GraphAutomorphismGroup[g], the elements of which may then be extracted using GroupElements. A number of software implementations exist for computing graph automorphisms, including nauty by Brendan McKay and SAUCY2, the latter of which performs several orders of magnitude faster than other implementations based on empirical..
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 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 -centipede graph, -centipede tree, or simply "-centipede," is the tree on nodes obtained by joining the bottoms of copies of the path graph laid in a row with edges. It is therefore isomorphic to the -firecracker graph, with special cases summarized in the table below.graph1path graph 2path graph 3E graphThe rank polynomial of the centipede is given by
A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form(1)where is the partition function P and is the floor function. A generating function for is given by(2)(3)(4)where is a q-Pochhammer symbol.Not all spiders are caterpillar graphs, norare all spiders lobster graphs.
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 (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 helm graph is the graph obtained from an -wheel graph by adjoining a pendant edge at each node of the cycle.Helm graphs are graceful (Gallian 2018), with the odd case of established by Koh et al. 1980 and the even case by Ayel and Favaron (1984). The helm graph is perfect only for and even .Precomputed properties of helm graphs are available in the Wolfram Language using GraphData["Helm", n, k].The -Helm graph has chromatic polynomial, independence polynomial, and matching polynomial given by(1)(2)(3)where . These correspond to recurrence equations (together with for the rank polynomial) of(4)(5)(6)(7)
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",..
An -firecracker is a graph obtained by the concatenation of -stars by linking one leaf from each (Chen et al. 1997, Gallian 2007).Firecracker graphs are graceful (Chen et al.1997, Gallian 2018).Precomputed properties of firecrackers are implemented in the Wolfram Language as GraphData["Firecracker", n, k].
The -tadpole graph, also called a dragon graph (Truszczyński 1984) or kite graph (Kim and Park 2006), is the graph obtained by joining a cycle graph to a path graph with a bridge.The -tadpole graph is sometimes known as the -pan graph. The particular cases of the - and -tadpole graphs are also known as the paw graph and banner graph, respectively (ISGCI).Precomputed properties of tadpole graphs are available in the Wolfram Language as GraphData["Tadpole", m, n].Koh et al. (1980) showed that -tadpole graphs are graceful for , 1, or 3 (mod 4) and conjectured that all tadpole graphs are graceful (Gallian 2018). Guo (1994) apparently completed the proof by filling in the missing case in the process of showing that tadpoles are graceful when or 2 (mod 4) (Gallian 2018).
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 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 complete bipartite graph is a tree known as the "claw." It is isomorphic to the star graph , and is sometimes known as the Y graph (Horton and Bouwer 1991; Biggs 1993, p. 147).More generally, the star graph is sometimes also known as a "claw" (Hoffmann 1960; Harary 1994, p. 17).The claw graph has chromatic number 2 and chromatic polynomialIts graph spectrum is .A graph that does not contain the claw as an inducedsubgraph is called a claw-free graph.
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 generalized Petersen graph , also denoted (Biggs 1993, p. 119; Pemmaraju and Skiena 2003, p. 215), for and is a connected cubic graph consisting of an inner star polygon (circulant graph ) and an outer regular polygon (cycle graph ) with corresponding vertices in the inner and outer polygons connected with edges. These graphs were introduced by Coxeter (1950) and named by Watkins (1969).Since the generalized Petersen graph is cubic, , where is the edge count and is the vertex count. More specifically, has nodes and edges. Generalized Petersen graphs are implemented in the Wolfram Language as PetersenGraph[k, n] and their properties are available using GraphData["GeneralizedPetersen", k, n].Generalized Petersen graphs may be further generalized to Igraphs.For odd, is isomorphic to . So, for example, , , , , and so on. The numbers of nonisomorphic generalized Petersen graphs on , 8, ... nodes are 1, 1, 2, 2, 2, 3,..
"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.