The knight graph is a graph on vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other).The number of edges in the knight graph is (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).Knight graphs are bipartite and therefore areperfect.The following table summarizes some named graph complements of knight graphs.-knight graph-queen graph-knight graph-queen graphThe knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].Closed formulas for the numbers of -graph cycles of the knight graph are given by for odd and(1)(E. Weisstein, Nov. 16, 2014).A knight's path is a sequence of moves by a..
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 graph is a hypotraceable graph if has no Hamiltonian path (i.e., it is not a traceable graph), but has a Hamiltonian path (i.e., is a traceable graph) for every (Bondy and Murty 1976, p. 61).There are no hypotraceable graphs on ten or fewer nodes (E. Weisstein, Dec. 11, 2013). In fact, the nonexistence of hypotraceable graphs on small numbers of vertices led T. Gallai to conjecture that no such graphs exist. This conjecture was refuted when a hypotraceable graph with 40 vertices was subsequently found by Horton (Grünbaum 1974, Thomassen 1974). Thomassen (1974) then showed that there exists a hypotraceable graph with vertices for , 37, 39, 40, and all . The smallest of these is the 34-vertex Thomassen graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).Walter (1969) gave an example of a connected graph in which the longest paths do not have a vertex in common, a property shared by hypotraceable..
An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736), the first few of which are illustrated above.The corresponding numbers of connected Eulerian graphs are 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS A003049; Robinson 1969; Liskovec 1972; Harary and Palmer 1973, p. 117), the first few of which are illustrated above.Some care is needed in interpreting the term, however, since some authors define an Euler graph as a different object, namely a graph for which all vertices are of even degree (motivated by the following theorem). Euler showed (without proof) that a connected simple graph is Eulerian iff it has no graph vertices of odd degree (i.e., all vertices are of even degree). While the number of connected Euler graphs on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for disconnected graphs since..
The term "Euler graph" is sometimes used to denote a graph for which all vertices are of even degree (e.g., Seshu and Reed 1961). Note that this definition is different from that of an Eulerian graph, though the two are sometimes used interchangeably and are the same for connected graphs.The numbers of Euler graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 16, 54, 243, 243, 2038, ... (OEIS A002854; Robinson 1969; Mallows and Sloane 1975; Buekenhout 1995, p. 881; Colbourn and Dinitz 1996, p. 687), the first few of which are illustrated above. There is an explicit formula giving these numbers.There are more Euler graphs than Eulerian graphs since there exist disconnected graphs having multiple disjoint cycles with each node even but for which no single cycle passes through all edges. The numbers of Euler-but-not-Eulerian graphs on , 2, ... nodes are 0, 0, 0, 0, 0, 1, 2, 7, 20, 76, 334, 2498, ... (OEIS A189771), the first few of which are..
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..
A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData["PlanarHypohamiltonian", 162] and GraphData["PlanarHypohamiltonian", 186], respectively.Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphson 154 vertices, as well as on all vertex counts greater than or equal to 156.Using the 70-node Araya-Wiener graph, a 340-nodecubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).Holton and Sheehan (1993) asked if there exists an integer such that a cubic planar hypotraceable..
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.
There are several definitions of "almost Hamiltonian" in use.As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on nodes having Hamiltonian number .As defined by Sanders (1987), a graph with vertices is almost Hamiltonian if every subset of vertices is contained in a circuit, a definition which is similar to that for a maximally nonhamiltonian graph.This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360), the first few of which are illustrated above.Punnim et al. (2007) showed that the generalized Petersen graph is almost Hamiltonian iff and .Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's graph is the unique almost Hamiltonian cubic graph on..
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).
A simplex, sometimes called a hypertetrahedron (Buekenhout and Parker 1998), is the generalization of a tetrahedral region of space to dimensions. The boundary of a -simplex has 0-faces (polytope vertices), 1-faces (polytope edges), and -faces, where is a binomial coefficient. An -dimensional simplex can be denoted using the Schläfli symbol . The simplex is so-named because it represents the simplest possible polytope in any given space.The content (i.e., hypervolume) of a simplex can be computedusing the Cayley-Menger determinant.In one dimension, the simplex is the line segment . In two dimensions, the simplex is the convex hull of the equilateral triangle. In three dimensions, the simplex is the convex hull of the tetrahedron. The simplex in four dimensions (the pentatope) is a regular tetrahedron in which a point along the fourth dimension through the center of is chosen so that . The regular simplex in dimensions with is denoted..
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 matchstick graph is a simple graph which has a graph embedding that is planar, for which all distances between vertices have unit distance, and which is non-degenerate (so no vertices are coincident, no edges cross or overlap, and no vertices are coincident with edges on which they are not incident).A matchstick graph is therefore both planar and unit-distance, but a planar unit-distance graph may fail to be a matchstick graph if a single embedding cannot be constructed having both properties. Examples include the prism graphs and Moser spindle, with the sole 6-vertex connected planar unit-distance non-matchstick graph being the 3-prism graph . The numbers of connected graphs on , 2, ... vertices that are planar and unit-distance but not matchstick are 0, 0, 0, 0, 0, 1, 13, ... (E. Weisstein, Apr. 30, 2018), where the 7-vertex examples are illustrated above.The numbers of connected matchstick graphs on , 2, ... nodes are 1, 1, 2,..
Two nonisomorphic graphs can share the same graph spectrum, i.e., have the same eigenvalues of their adjacency matrices. Such graphs are called cospectral. For example, the graph union and star graph , illustrated above, both have spectrum (Skiena 1990, p. 85). This is the smallest pair of simple graphs that are cospectral. Determining which graphs are uniquely determined by their spectra is in general a very hard problem.Only a small fraction of graphs are known to be so determined, but it is conceivablethat almost all graphs have this property (van Dam and Haemers 2002).In the Wolfram Language, graphs knownto be determined by their spectra are identified as GraphData["DeterminedBySpectrum"].The numbers of simple graphs on , 2, ... nodes that are determined by spectrum are 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925), while the corresponding numbers not determined by spectrum are 0, 0, 0, 0, 2, 10, 110, 1722,..
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 caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree are surrounded by at most two nodes of degree two or greater.Caterpillar graphs are graceful.The number of caterpillar trees on nodes iswhere is the floor function (Harary and Schwenk 1973). For , 2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418). The first few caterpillars are illustrated above.The number of noncaterpillar trees on , 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471). The noncaterpillar trees on nodes are illustrated above.
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].
LCF notation is a concise and convenient notation devised by Joshua Lederberg (winner of the 1958 Nobel Prize in Physiology and Medicine) for the representation of cubic Hamiltonian graphs (Lederberg 1965). The notation was subsequently modified by Frucht (1976) and Coxeter et al. (1981), and hence was dubbed "LCF notation" by Frucht (1976). Pegg (2003) used the notation to describe many of the cubic symmetric graphs. The notation only applies to Hamiltonian graphs, since it achieves its symmetry and conciseness by placing a Hamiltonian cycle in a circular embedding and then connecting specified pairs of nodes with edges.For example, the notation describes the cubical graph illustrated above. To see how this works, begin with the cycle graph . Beginning with a vertex , count three vertices clockwise () to and connect it to with an edge. Now advance to , count three vertices counterclockwise () to vertex , and connect and with an edge...
An integral graph is defined as a graph whose graph spectrum consists entirely of integers. The notion was first introduced by Harary and Schwenk (1974). The numbers of simple integral graphs on , 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small .The numbers of connected simple integral graphs on , 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small .The following table lists common graph classes and the their members which are integral.graphintegral for of the formantiprism graph3complete graph allcycle graph 2, 3, 4, 6empty graphallprism graph3, 4, 6star graph wheel graph 4The following table lists some special named graphs that are integral and gives their spectra.graphgraph spectrum16-cell24-cellClebsch graphcubical graphcuboctahedral graphDesargues graphHall-Janko graphHoffman graphHoffman-Singleton graphLevi graphM22 graphMcLaughlin..
Given a set , let be the set of neighbors of . Then the bipartite graph with bipartitions and has a perfect matching iff for all subsets of .
The thickness (or depth) (Skiena 1990, p. 251; Beineke 1997) or (Harary 1994, p. 120) of a graph is the minimum number of planar subgraphs of needed such that the graph union (Skiena 1990, p. 251).The thickness of a planar graph is therefore , and the thickness of a nonplanar graph satisfies .A lower bound for the thickness of a graph is given by(1)where is the number of edges, is the number vertices, and is the ceiling function (Skiena 1990, p. 251). The example above shows a decomposition of the complete graph into three planar subgraphs. This decomposition is minimal, so , in agreement with the bound .The thickness of a complete graph satisfies(2)except for (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997). For , 2, ..., the thicknesses are therefore 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, ... (OEIS A124156).The thickness of a complete bipartite graph is given by(3)except possibly when and are both odd, and with there..
The skewness of a graph is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted (Cimikowski 1992).A graph with has toroidal crossing number . (However, there exist graphs with that still have .) satisfies(1)where is the vertex count of and its edge count (Cimikowski 1992).The skewness of a disconnected graph is equalto the sum of skewnesses of its connected components.The skewness of a complete graph is given by(2)of the complete bipartite graph by(3)and of the hypercube graph by(4)(Cimikowski 1992).
The triangular snake graph is the graph on vertices with odd defined by starting with the path graph and adding edges for , ..., . The first few are illustrated above, and special cases are summarized in the following table.1singleton graph 3triangle graph 5butterfly graphTriangular snakes are unit-distance and matchstick by construction, perfect. They are graceful when the number of triangles is congruent to 0 or 1 (mod 4) (Moulton 1989, Gallian 2018), which is equivalent to when .
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).
"The" Y-graph is another term used to refer to a clawgraph.The term "Y-graph" is also used to refer to a graph expansion with the Y graph as its base (e.g., Horton and Bouwer 1991). There are exactly four graph expansions with Y-graph base that are symmetric (Biggs 1993, p. 147).graphexpansion 28Coxeter graph(7; 1, 2, 4)56cubic symmetric graph (14; 1, 3, 5)112cubic symmetric graph (28; 1, 3, 9)224cubic symmetric graph (56; 1, 9, 25)
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..
Given a planar graph , its geometric dual is constructed by placing a vertex in each region of (including the exterior region) and, if two regions have an edge in common, joining the corresponding vertices by an edge crossing only . The result is always a planar pseudograph. However, an abstract graph with more than one embedding on the sphere can give rise to more than one dual.Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph.
"The" graph is the path graph on two vertices: .An -graph for and is a generalization of a generalized Petersen graph and has vertex setand edge setwhere the subscripts are read modulo (Bouwer et al. 1988, itnik et al. ). Such graphs can be constructed by graph expansion on .If the restriction is relaxed to allow and to equal , gives the ladder rung graph and gives the sunlet graph .Two -graphs and are isomorphic iff there exists an integer relatively prime to such that either or (Boben et al. 2005, Horvat et al. 2012, itnik 2012).The graph is connected iff . If , then the graph consists of copies of (itnik et al. 2012).The -graph corresponds to copies of the graph The following table summarizes special named -graphs and classes of named -graphs.graphcubical graph Petersen graph Dürer graphMöbius-Kantor graphdodecahedral graphDesargues graphNauru graphprism graph generalized Petersen graph All -graphs..
Given any tree having vertices of vertex degrees of 1 and 3 only, form an -expansion by taking disjoint copies of and joining corresponding leaves by an -cycle where, however, the th leaf on the th copy need not be connected to the th leaf on the st copy, but will in general be connected to the th copy. The set of values are known as the steps.The resulting graphs are always cubic, and there exist exactly 13 graph expansions that are symmetric as well, as summarized in the following table (Biggs 1993, p. 147). E. Gerbracht (pers. comm., Jan. 29, 2010) has shown that all the graphs in this table are unit-distance.graphFostergeneralized Petersen graphbase graphexpansion 8cubical graph I graph(4; 1, 1)10Petersen graphI graph(5; 1, 2)16Möbius-Kantor graphI graph(8; 1, 3)20dodecahedral graphI graph(10; 1, 2)20Desargues graphI graph(10; 1, 3)24Nauru graphI graph(12; 1, 5)28Coxeter graphY graph(7; 1, 2, 4)48cubic symmetric..
A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with nodes has graph edges. Conversely, a connected graph with nodes and edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).The points of connection are known..
Given matches (i.e., rigid unit line segments), find the number of topologically distinct planar arrangements which can be made (Gardner 1991). In this problem, two matches laid end-to-end with no third match at their meeting point are considered equivalent to a single match, so triangles are equivalent to squares, -match tails are equivalent to 1-match tails, etc.Solutions to the match problem are planar topological graphs on edges, and the first few values for , 1, 3, 5, 10, 19, 39, ... (OEIS A003055).
Let denote a configuration with points and lines ("blocks") . Then the incidence graph , also called the Levi graph, of a configuration is a bipartite graph with "black" vertices , "white" vertices , and an edge between and iff (Coxeter 1950, Pisanski and Randić 2000).The following table summarizes the incidence graphs of some common configurations.nameconfigurationincidence graphCox configuration-hypercube graphCoxeter configurationNauru graphCremona-Richmond configurationLevi graphDesargues configurationDesargues graphdouble sixesSchläfli double sixes graphFano planeHeawood graphGray configurationGray graphKummer configurationKummer graphMiquel configurationrhombic dodecahedral graphMöbius-Kantor configurationMöbius-Kantor graphPappus configurationPappus graphPasch configurationPasch graphReye configurationReye graphDual configurations..
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 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..
For a permutation in the symmetric group , the -permutation graph of a labeled graph is the graph union of two disjoint copies of (say, and ), together with the lines joining point of with of (Harary 1994, p. 175).Skiena (1990, p. 28) defines a permutation graph as a graph whose edges correspond exactly to being a permutation inversion is some permutation , i.e., but occurs before in . The above graph corresponds to the permutation , which has permutation inversion . Permutation graphs are implemented as PermutationGraph[p] in the Wolfram Language package Combinatorica` .
A transposition graph is a graph whose nodes correspond to permutations and edges to permutations that differ by exactly one transposition (Skiena 1990, p. 9, Clark 2005).The transposition graph has vertex count , edge count (for ), and is regular of degree (Clark 2005). All cycles in transposition graphs are of even length, making them bipartite.The transposition graph of a multiset is always Hamiltonian(Chase 1973).Special cases are summarized in the table below.1singleton graph 22-path graph 3utility graph 4Reye graph
"The" butterfly graph is a name sometimes given to the 5-vertex graph illustrated above. This graph is also known as the "bowtie graph" (West 2000, p. 12) and is the triangular snake graph . The butterfly graph is ungraceful (Horton 2003). It is implemented in the Wolfram Language as GraphData["ButterflyGraph"].A different type of butterfly graph is defined as follows. The -dimensional butterfly graph is a directed graph whose vertices are pairs , where is a binary string of length and is an integer in the range 0 to and with directed edges from vertex to iff is identical to in all bits with the possible exception of the th bit counted from the left.The -dimensional butterfly graph has vertices and edges, and can be generated in the Wolfram Language using ButterflyGraph[n, b] (with )...
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..
A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with , 2, ... nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, ... (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.The corresponding numbers of planar connected graphs are 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, ... (OEIS A003094; Steinbach 1990, p. 131)There appears to be no term in standard use for a graph with graph crossing number 1 (the terms "almost planar" and "1-planar" are used in the literature for other concepts).Note that while graph planarity is an inherent property of a graph, it is still sometimes possible to draw nonplanar embeddings of planar graphs. For example, the two embeddings above both correspond to the planar tetrahedral graph, but while the left embedding is planar, the right embedding is not.A planar embedding of a..
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 Icosian game, also called the Hamiltonian game (Ball and Coxeter 1987, p. 262), is the problem of finding a Hamiltonian cycle along the edges of an dodecahedron, i.e., a path such that every vertex is visited a single time, no edge is visited twice, and the ending point is the same as the starting point (left figure). The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph, illustrated above (right figure). The Icosian Game was invented in 1857 by William Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25 pounds, and the game was subsequently marketed in Europe in a number of forms (Gardner 1957).A graph having a Hamiltonian cycle, i.e., on which the Icosian game may be played, is said to be a Hamiltonian graph. While the skeletons of all the Platonic solids and Archimedean solids (i.e., the Platonic graphs and Archimedean graphs, respectively) are Hamiltonian, the same is..
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).
A cactus graph, sometimes also called a cactus tree, a mixed Husimi tree, or a polygonal cactus with bridges, is a connected graph in which any two graph cycles have no edge in common. Equivalently, it is a connected graph in which any two (simple) cycles have at most one vertex in common.The inequalitywhere is the circuit rank and is the total number of undirected graph cycles holds for a connected graph iff it is a cactus graph (Volkmann 1996).Every cycle of a cactus graph is therefore chordless. However, there exist graphs (e.g., the -graph and Pasch graph) whose cycles are all chordless but which are not cactus graphs.Every cactus graph is a unit-distance graph(Erdős et al. 1965).Every pseudotree is a cactus graph.The numbers of cactus graphs on 1, 2, ... nodes are 1, 1, 2, 4, 9, 23, 63, 188, ...(OEIS A000083)...
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.
Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture). The Horton graph on 96 nodes, illustrated above, provided the first counterexample (Bondy and Murty 1976, p. 240).Horton (1982) subsequently found a counterexample on 92 nodes, and two smaller (nonisomorphic) counterexamples on 78 nodes were found by Ellingham (1981, 1982b) and Owens (1983). Ellingham and Horton (1983) subsequently found a counterexample graph on 54 nodes and 81 edges. The smallest currently known counterexample is the 50-node Georges graph (Georges 1989; Grünbaum 2006, 2009).These small known counterexamples are summarized in the following table and illustrated above.namereference50Georges graphGeorges (1989), Grünbaum (2006, 2009)54Ellingham-Horton 54-graphEllingham and Horton (1983)78Ellingham-Horton 78-graphEllingham (1981, 1982)78Owens graphOwens (1983)92Horton 92-graphHorton..
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.
Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of connected cubic nonhamiltonian graphs on , 12, ... are 2, 5, 35, 219, 1666, ... (OEIS A164919). The figure above shows some nonhamiltonian connected cubic graphs that are not snarks.Cubic nonhamiltonian graphs are of special interest because of Tait's Hamiltonian graph conjecture. The cubic polyhedral nonhamiltonian graphs illustrated above all provide counterexamples to this conjecture.The Horton graphs and Ellingham-Horton graphs are examples of 3-connected bicubic graphs that provided counterexamples to the Tutte conjecture.
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
Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Frink 1926; König 1936; Skiena 1990, p. 244). In fact, this theorem can be extended to read, "every cubic graph with 0, 1, or 2 bridges has a perfect matching."The graph above shows the smallest counterexample for 3 bridges, namely a connected cubic graph on 16 vertices having no perfect matchings. This graph is implemented in the Wolfram Language as GraphData["Cubic", 16, 14].Errera (1922) strengthened Petersen's theorem by proving that if all bridges of a connected cubic graph lie on a single path of , then has a perfect matching.
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.
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"].
Heule graphs are a set of unit-distance graphs with chromatic number five derived by Marijn Heule in April-May 2018 from the 1581-vertex de Grey Graph (Heule 2018). As of July 2019, they provide the smallest known examples that establish the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) as 5, 6, or 7. The first of these graphs were discovered in the days and weeks following publication of the de Grey graph and are summarized in the following table, with the 529-vertex graph being discovered more than a year later and after roughly 100,000 CPU-hours of computation (Heule 2019). The first few are illustrated above.vertex countedge countdiscovery date8744461Apr. 14, 20188264273Apr. 16, 20188034144Apr. 30, 20186333166May 6, 20186103000May 14, 20185532722May 30, 20185292670Jul. 1, 2019..
The de Grey graph is the name given here to the 1581-vertex graph presented in de Grey (2018) which demonstrated that the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) is at least 5. This graph (together with the larger graphs from which it was derived) provided the first known examples of a unit-distance graph with chromatic number 5.Smaller unit-distance graphs with chromatic number 5, here called Heule graphs, were computationally derived from the de Grey graph by Marijn Heule.
Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. A graph with edge chromatic number equal to is known as a class 2 graph.Class 2 graphs include the Petersen graph, complete graphs for , 5, 7, ..., and the snarks.All regular graphs with an odd number of nodes are class 2 by parity. Such graphs automatically have an even number of edges per vertex.A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph is trivially class 2 ifwhere is the matching number, the maximum vertex degree, and the edge count of .The following table summarizes some named class 2 graphs.graph triangle graph3pentatope graph5Petersen graph10first Blanuša snark18second Blanuša snark18Robertson graph19flower snark2025-Grünbaum graph25Doyle graph27double star snark30Szekeres snark50McLaughlin graph275The..
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.
Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. A graph with edge chromatic number equal to is known as a class 1 graph.König's line coloring theorem states that all bipartite graphs are class 1. All cubic Hamiltonian graphs are class 1, as are planar graphs with maximum vertex degree (Cole and Kowalik 2008).Class 1 graphs have both edge chromatic number and fractional edge chromatic number equal to .Families of non-bipartite graphs that appear to be class 1 (or at least whose smallest members are all class 1) include king, Lindgren-Sousselier, and windmill graphs (S. Wagon, pers. comm., Oct. 27-28, 2011). Keller graphs are class 1 (Jarnicki et al. 2015). Aubert and Schneider (1982) showed that rook graphs admit Hamiltonian decomposition, meaning they are class 1 when they have even vertex count and class 2 when they have odd vertex count (because..
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).
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with . The illustration above shows some bipartite graphs, with vertices in each graph colored based on to which of the two disjoint sets they belong.Bipartite graphs are equivalent to two-colorable graphs. All acyclic graphs are bipartite. A cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).Families of of bipartite graphs include 1. acyclic graphs (i.e., treesand forests), 2. book graphs , 3. crossed prism graphs, 4. crown graphs , 5. cycle graphs , 6. gear graphs, 7. grid graphs, 8. Haar graphs, 9. Hadamard graphs, 10. hypercube graphs , 11. knight graphs, 12. ladder graphs, 13. ladder rung graphs (which are forests). 14. path graphs (which are trees), 15. Mongolian tent graphs, 16. Sierpiński..
A bicolorable graph is a graph with chromatic number . A graph is bicolorable iff it has no odd graph cycles (König 1950, p. 170; Skiena 1990, p. 213; Harary 1994, p. 127). Bicolorable graphs are equivalent to bipartite graphs (Skiena 1990, p. 213). The numbers of bipartite graphs on , 2, ... nodes are 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS A033995). A graph can be tested for being bicolorable using BipartiteGraphQ[g], and one of its two bipartite sets of vertices can be found using FindIndependentVertexSet[g][].The following table lists some named bicolorable graphs.graph singleton graph1square graph4claw graph4utility graph6cubical graph8Herschel graph11Franklin graph12Heawood graph14tesseract graph16Möbius-Kantor graph16Hoffman graph16Pappus graph18Folkman graph20Desargues graph20truncated octahedral graph24Walther graph25Levi graph30Dyck graph32great rhombicuboctahedral..
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].
A perfect graph is a graph such that for every induced subgraph of , the clique number equals the chromatic number, i.e., . A graph that is not a perfect graph is called an imperfect graph (Godsil and Royle 2001, p. 142).A graph for which (without any requirement that this condition also hold on induced subgraphs) is called a weakly perfect graph. All perfect graphs are therefore weakly perfect by definition.A graph is strongly perfect if every induced subgraph has an independent set meeting all maximal cliques of . While all strongly perfect graphs are perfect, the converse is not necessarily true. Since every -free graph (where is a path graph) is strongly perfect (Ravindra 1999) and every strongly perfect graph is perfect, if a graph is -free, it is perfect.Perfect graphs were introduced by Berge (1973) motivated in part by determining the Shannon capacity of graphs (Bohman 2003). Note that rather confusingly, perfect graphs are distinct..
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.
The neighborhood graph of a given graph from a vertex is the subgraph induced by the neighborhood of a graph from vertex , most commonly including itself. Such graphs are sometimes also known in more recent literature as ego graphs or ego-centered networks (Newman 2010, pp. 44-46).A graph for which the neighborhood graph at each point excluding the point itself is isomorphic to a graph is said to be a local H graph, or simply "locally ."Neighborhood graphs are implemented in the Wolfram Language as NeighborhoodGraph[g, v].
A polyhedral graph corresponding to the skeleton of a Platonic solid. The five platonic graphs, the tetrahedral graph, cubical graph, octahedral graph, dodecahedral graph, and icosahedral graph, are illustrated above. They are special cases of Schlegel graphs.Platonic graphs are graceful (Gardner 1983, pp. 158and 163-164).The following table summarizes the Platonic graphs and some of their properties.graph regularityHamiltonianEulerianvertex-transitiveedge-transitivecubical graphcubic81248yesnoyesyesdodecahedral graphcubic2030120yesnoyesyesicosahedral graphquintic1230120yesnoyesyesoctahedral graphquartic61248yesyesyesyestetrahedral graphcubic4624yesnoyesyes
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)
A wheel graph of order , sometimes simply called an -wheel (Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78), is a graph that contains a cycle of order , and for which every graph vertex in the cycle is connected to one other graph vertex (which is known as the hub). The edges of a wheel which include the hub are called spokes (Skiena 1990, p. 146). The wheel can be defined as the graph , where is the singleton graph and is the cycle graph. Note that there are two conventions for the indexing for wheel graphs, with some authors (e.g., Gallian 2007), adopting the convention that denotes the wheel graph on nodes.The tetrahedral graph (i.e., ) is isomorphic to , and is isomorphic to the complete tripartite graph . In general, the -wheel graph is the skeleton of an -pyramid. is one of the two graphs obtained by removing two edges from the pentatope graph , the other being the house X graph.Wheel graphs are graceful (Frucht..
The -pan graph is the graph obtained by joining a cycle graph to a singleton graph with a bridge. The -pan graph is therefore isomorphic with the -tadpole graph. The special case of the 3-pan graph is sometimes known as the paw graph and the 4-pan graph as the banner graph (ISGCI).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), thus establishing that pan graphs are graceful.The fact that the -pan graphs, corresponding to -tadpole graphs, are graceful for , 2 (mod 4) follows immediately from adding the label to the "handle" vertex adjacent to the verex with label 0 in a cycle graph labeling.Precomputed properties of pan graphs are available in the Wolfram Language as GraphData["Pan",..
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",..
Koh et al. (1980) and Gallian (2007) define a web graph as a stacked prism graph with the edges of the outer cycle removed.Web graphs are graceful.Precomputed properties of web graphs are available in the Wolfram Language as GraphData["Web", n].The term "web graph" is also used (e.g., Horvat and Pisanski 2010) to refer to the stacked prism graph itself, where is a cycle graph, is a path graph, and denotes a graph Cartesian product.The bipartite double graph of the web graph for odd is .
"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..
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" 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..
A Mongolian tent graph is defined as the graph obtained from the graph Cartesian product for odd by adding an extra vertex above the graph and joining every other vertex of the top row to the additional vertex (Lee 1985; Gallian 2011, p. 14).Mongolian tent graphs are graceful (Lee 1985, Gallian2018).A Mongolian village is defined as a graph formed by successively amalgamating copies of Mongolian tents with the same number of rows so that adjacent tents share a column.Precomputed properties of Mongolian tent graphs are implemented in the Wolfram Language as GraphData["MongolianTent", m, n].
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...
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 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 -sunlet graph is the graph on vertices obtained by attaching pendant edges to a cycle graph (ISGCI), i.e., the coronas (Frucht 1979). Sunlet graphs have also been called crown graphs (e.g., Gallian 2018), a terminology that conflicts with the use of the term "crown graph" in this work to refer to a rook complement graph .Sunlet graphs are trivially unit-distance graphs, as well as matchstick graphs. They are also graceful (Frucht 1979).Note that Wallis (2000) and Anitha and Lekshmi (2008) use the term "-sun" graph to refer to sunlet graphs, whereas ISGCI and other authors reserve that term for a different type of graph.The 3-sunlet graph is also known as the net graph.If the restriction in the I graph is loosened, the -sunlet graph corresponds to .
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..
A complete bipartite graph, sometimes also called a complete bicolored graph (Erdős et al. 1965) or complete bigraph, is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent. If there are and graph vertices in the two sets, the complete bipartite graph is denoted . The above figures show and . is also known as the utility graph (and is the circulant graph ), and is the unique 4-cage graph. is a Cayley graph. A complete bipartite graph is a circulant graph (Skiena 1990, p. 99), specifically , where is the floor function.Special cases of are summarized in the table below.path graph path graph claw graphstar graph square graph utility graphThe numbers of (directed) Hamiltonian cycles for the graph with , 2, ... are 0, 2, 12, 144, 2880, 86400, 3628800, 203212800, ... (OEIS A143248), where..
The star graph of order , sometimes simply known as an "-star" (Harary 1994, pp. 17-18; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 23), is a tree on nodes with one node having vertex degree and the other having vertex degree 1. The star graph is therefore isomorphic to the complete bipartite graph (Skiena 1990, p. 146).Note that there are two conventions for the indexing for star graphs, with some authors (e.g., Gallian 2007), adopting the convention that denotes the star graph on nodes. is isomorphic to "the" claw graph. A star graph is sometimes termed a "claw" (Hoffman 1960) or a "cherry" (Erdős and Rényi 1963; Harary 1994, p. 17).Star graphs are always graceful. Star graphs can be constructed in the Wolfram Language using StarGraph[n]. Precomputed properties of star graphs are available via GraphData["Star", n].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..
A prism graph, denoted , (Gallian 1987), or (Hladnik et al. 2002), and sometimes also called a circular ladder graph and denoted (Gross and Yellen 1999, p. 14), is a graph corresponding to the skeleton of an -prism. Prism graphs are therefore both planar and polyhedral. An -prism graph has nodes and edges, and is equivalent to the generalized Petersen graph . For odd , the -prism is isomorphic to the circulant graph , as can be seen by rotating the inner cycle by and increasing its radius to equal that of the outer cycle in the top embeddings above. In addition, for odd , is isomorphic to , , ..., . is isomorphic to the graph Cartesian product , where is the path graph on two nodes and is the cycle graph on nodes. As a result, it is a unit-distance graph (Horvat and Pisanski 2010).The prism graph is equivalent to the Cayley graph of the dihedral group with respect to the generating set (Biggs 1993, p. 126).The prism graph is the line graph of the complete..
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.
Given a planar graph , a geometric dual graph and combinatorial dual graph can be defined. Whitney showed that these are equivalent (Harary 1994), so that one may speak of "the" dual graph . The illustration above shows the process of constructing a geometric dual graph.Polyhedral graphs have unique dual graphs. While some nonpolyhedral planar graphs also have a unique dual, a general planar graph has multiple dual graphs depending on the choice of planar drawing. A planar graph has a unique embedding, and consequently a unique dual, iff it is a subdivision of a polyhedral graph. The complete bipartite graph is an example of a planar nonpolyhedral graph that is not 3-vertex-connected but whose embeddings are all isomorphic, meaning its dual graphs are also isomorphic.The dual graph of a polyhedral graph has graph vertices each of which corresponds to a face of and each of whose faces corresponds to a graph vertex of . Two nodes in are connected..
"The" H graph is the tree on 6 vertices illustrated above. It is implemented in the Wolfram Language as GraphData["HGraph"].The term "H-graph" is also used to refer to a graph expansion with the 6-vertex H graph as its base (e.g., Horton and Bouwer 1991). There are exactly two graph expansions with H-graph base that are symmetric (Biggs 1993, p. 147).graphexpansion 102Biggs-Smith graph (17; 3, 5, 6, 7)204cubic symmetric graph (34; 3, 5, 7, 11)
Let be the cycle rank of a graph , be the cocycle rank, and the relative complement of a subgraph of be defined as that subgraph obtained by deleting the lines of . Then a graph is a combinatorial dual of if there is a one-to-one correspondence between their sets of lines such that for any choice and of corresponding subsets of lines,where is the subgraph of with the line set .Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph. Also, a graph is planar iff it has a combinatorial dual (Harary 1994, p. 115).
Isomorphic factorization colors the edges a given graph with colors so that the colored subgraphs are isomorphic. The graph is then -splittable, with as the divisor, and the subgraph as the factor.When a complete graph is 2-split, a self-complementary graph results. Similarly, an -regular class 1 graph can be -split into graphs consisting of disconnected edges, making the edge chromatic number.The complete graph can be 3-split into identical planar graphs.Some Ramsey numbers have been bounded via isomorphic factorizations. For instance, the complete graph has the Clebsch graph as a factor, proving (Gardner 1989). That is, the complete graph on 16 points can be three-colored so that no triangle of a single color appears. (In 1955, was proven.)In addition, can be 8-split with the Petersen graph as a factor, or 5-split with a doubled cubical graph as a factor (shown by Exoo in 2005).The Hoffman-Singleton graph is 7-splittable into edges (shown..
Let be the smallest dimension of a hypercube such that if the lines joining all pairs of corners are two-colored for any , a complete graph of one color with coplanar vertices will be forced. Stated colloquially, this definition is equivalent to considering every possible committee from some number of people and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find the smallest that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees (Hoffman 1998, p. 54).An answer was proved to exist by Graham and Rothschild (1971), who also provided the best known upper bound, given by(1)where Graham's number is recursively defined by(2)and(3)Here, is the so-called Knuth up-arrow notation. is often cited as the largest number that has ever been put to practical use (Exoo 2003).In chained arrow notation, satisfies..
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.
Robertson's apex graph is the 15-vertex graph illustrated above constructed by Neil Robertson as an example of an apex graph that is not -reducible.The graph may be constructed by adding an apex vertex which is connected to each degree-3 vertex of the (planar) rhombic dodecahedral graph, or by contracting two opposite vertices of the tesseract graph.
The dimension of a graph is the smallest dimension of Euclidean -space in which it can be embedded with every edge length equal to 1 and every vertex position distinct (but where edges may cross or overlap; Erdős et al. 1965).The singleton graph has graph dimension 0, the path graphs for have graph dimension 1, and in general, any graph with dimension 2 or less is said to be a unit-distance graph. The following table summarizes the graph dimensions for various families of parametrized graphs.graphdimensioncomplete bipartite graph complete graph cycle graph 2empty graph generalized Petersen graph 2grid graph hypercube graph path graph star graph wheel graph
A planar drawing of a planar graph in which only straight line segments are used to connect the graph vertices. Fáry (1948) showed that every planar graph has a planar straight line drawing with noncrossing edges (Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994), and such embeddings (with rectilinear crossing number 0) are sometimes known as a Fáry embedding.A planar straight line drawing of a planar graph can be constructed in the Wolfram Language using the "PlanarEmbedding" option to GraphLayout or in the Wolfram Language using PlanarGraph[g].de Fraysseix et al. (1988) give an algorithm for constructing a planar straight line graph for a planar graph of order by placing the vertices on a grid (Skiena 1990, p. 251).
A planar embedding of a planar graph is called a planar drawing, or sometimes a "plane graph" (Harary 1994, p. 103; Harborth and Möller 1994), "plane drawing" or "planar embedding."A planar straight line drawing of a planar graph can be constructed in the Wolfram Language using the "PlanarEmbedding" option to GraphLayout or using PlanarGraph[g].Precomputed planar embeddings of some graphs are available in the Wolfram Language as GraphData[g, "Images", "Planar"].
An apex graph, sometimes also called a nearly planar graph (though this term is also used in other contexts), is a graph that becomes planar by removal of a vertex. The set of vertices whose removal renders the graph planar is known as the apices of the graph. Planar graphs are themselves trivially apex graphs having all vertices as apices.Apex graphs differ from critical nonplanar graphs in that an apex graph requires only that there exist at least one vertex whose removal gives a planar graph, while a critical nonplanar graph requires that removal of each vertex gives a planar graph.Every apex graph has chromatic number .The numbers of apex graphs on , 2, ... vertices are 1, 2, 4, 11, 34, 155, 1026, 11666, 226916, ... (OEIS A215620), while the numbers of nonplanar apex graphs are 0, 0, 0, 0, 1, 13, 204, 4700, 147063, ... (OEIS A215621), with the only nonplanar apex graph on vertices being the complete graph . The 13 nonplanar apex graphs on six vertices are..
Let be a graph with graph vertices and graph edges on graph vertices without a -clique. Thenwhere is the edge count. (Note that the convention of Aigner (1995) of considering -cliques has been replaced with the apparently slightly more standard indexing by considering -cliques, providing consistency with the usual definition of Turán graphs.)The Turán graph is defined as the unique graph without a -clique having the maximum possible number of graph edges, namelywhere denotes the floor function.
An imperfect graph is a graph that is not perfect. Therefore, graphs with(1)where is the clique number and is the chromatic number are imperfect. A weaker form using a bound of states that a graph with(2)where is the independence number is imperfect.By the perfect graph theorem, applying the above to the graph complement gives that a graph with(3)where is the clique covering number is also imperfect.A graph is also imperfect iff either the graph or its complementhas a chordless cycle of odd order.Families of imperfect graphs include: 1. cycle graphs 2. fullerenes (which by definition contain an odd 5-cycle)3. king graphs with 4. helm graphs for odd 5. wheel graphs A list of imperfect graphs on small numbers of vertices is implemented in the Wolfram Language as GraphData["Imperfect"].The numbers of simple imperfect graphs on , 2, ... vertices are 0, 0, 0, 0, 1, 8, 138, 3459, ... (OEIS A187236).The numbers of connected imperfect graphs..
In algebraic topology, a -skeleton is a simplicial subcomplex of that is the collection of all simplices of of dimension at most , denoted .The graph obtained by replacing the faces of a polyhedron with its edges and vertices is therefore the skeleton of the polyhedron. The polyhedral graphs corresponding to the skeletons of Platonic solids are illustrated above. The number of topologically distinct skeletons with graph vertices for , 5, 6, ... are 1, 2, 7, 18, 52, ... (OEIS A006869).
Let be a group, and let be a set of group elements such that the identity element . The Cayley graph associated with is then defined as the directed graph having one vertex associated with each group element and directed edges whenever . The Cayley graph may depend on the choice of a generating set, and is connected iff generates (i.e., the set are group generators of ).Care is needed since the term "Cayley graph" is also used when is implicitly understood to be a set of generators for the group, in which case the graph is always connected (but in general, still dependent on the choice of generators). This sort of Cayley graph of a group may be computed in the Wolfram Language using CayleyGraph[G], where the generators used are those returned by GroupGenerators[G].To complicate matters further, undirected versions of proper directed Cayley graphs are also known as Cayley graphs.An undirected Cayley graph of a particular generating set of..
The word "rigid" has two different meaning when applied to a graph. Firstly, a rigid graph may refer to a graph having a graph automorphism group containing a single element.A framework (or graph) is rigid iff continuous motion of the points of the configuration maintaining the bar constraints comes from a family of motions of all Euclidean space which are distance-preserving. A graph that is not rigid is said to be flexible (Maehara 1992).For example, the cycle graph is rigid, while is flexible. An embedding of the bipartite graph in the plane is rigid unless its six vertices lie on a conic (Bolker and Roth 1980, Maehara 1992).A graph is (generically) -rigid if, for almost all (i.e., an open dense set of) configurations of , the framework is rigid in .Cauchy (1813) proved the rigidity theorem, one of the first results in rigidity theory. Although rigidity problems were of immense interest to engineers, intensive mathematical study of..
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 large Witt graph, also called the octad graph (Brouwer) or Witt graph (DistanceRegular.org), is the graph whose vertices are the 759 blocks of a Steiner system in which two blocks are adjacent whenever they are disjoint (Brouwer et al. 1989, p. 366).Perhaps the simplest construction is by selecting the 759 codewords of weight 8 of the extended binary Golay code and joining two words when they have disjoint support (i.e., if the codeword vectors are orthogonal).It is a distance-regular graph with intersection array and is also distance-transitive. It is an integral graph with graph spectrum . Its automorphism group has order , where is the largest Mathieu group. Its chromatic number is apparently unknown.The large Witt graph is implemented in the WolframLanguage as GraphData["LargeWittGraph"]...
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..
The Leonard graph is a distance-regular graph on 288 vertices (Brouwer et al. 1989, p. 369) with intersection array . It is however not distance-transitive. It has graph spectrum .The Leonard graph is implemented in the WolframLanguage as GraphData["LeonardGraph"].The two halved Leonard graphs are also distance-regular, both with intersection array .
The doubly truncated Witt graph is the graph on 330 vertices related to a 3- design (Brouwer et al. 1989, p. 367). The doubly truncated Witt graph can be constructed by removing all vectors of the large Witt design containing any two arbitrarily chosen symbols. Consider the 759 vertices of the large Witt graph as words of weight 8 in extended binary Golay. Call the octads, and view them as sets of size 8. Pick one coordinate position. 253 octads have a 1 there, 506 octads have a 0 there. Pick a second coordinate position. Of the 506, there are 176 with a 1 there, and 330 with a 0. The induced subgraph from 759, or from 506 on this 330 gives the doubly truncated Witt graph (A. E. Brouwer, pers. comm., Jun. 8, 2009).It is an integral graph with graph spectrum , is weakly regular with parameters . It is also distance-transitive with intersection array . The order of its automorphism group is , where is a Mathieu group.This graph is implemented..
A Turán graph, sometimes called a maximally saturated graph (Zykov 1952, Chao and Novacky 1982), with positive integer parameters and is a type of extremal graph on vertices originally considered by Turán (1941). There are unfortunately two different conventions for the index .In the more standard terminology (and that adopted here), the -Turán graph, sometimes also called a K-graph and variously denoted , (Gross and Yellen 2006, p. 476), (Chao and Novacky 1982), or (Pach and Agarwal 1995, p. 120), is the extremal graph on graph vertices that contains no -clique for (Chao and Novacky 1982; Diestel 1997, p. 149; Bollobás 1998, p. 108). In other words, the Turán graph has the maximum possible number of graph edges of any -vertex graph not containing a complete graph . The Turán graph is also the complete -partite graph on vertices whose partite sets are as nearly equal in..
A random graph is a graph in which properties such as the number of graph vertices, graph edges, and connections between them are determined in some random way. The graphs illustrated above are random graphs on 10 vertices with edge probabilities distributed uniformly in .Erdős and Rényi (1960) showed that for many monotone-increasing properties of random graphs, graphs of a size slightly less than a certain threshold are very unlikely to have the property, whereas graphs with a few more graph edges are almost certain to have it. This is known as a phase transition (Janson et al. 2000, p. 103). Almost all graphs are connected and nonplanar (Skiena 1990, p. 156).The Wolfram Language command RandomGraph[n, m] gives a pseudorandom graph with vertices and edges.
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..
The Harary graph is a particular example of a k-connected graph with graph vertices having the smallest possible number of edges. The smallest number of edges possible, as achieved by the Harary graph , is , where is the ceiling function (Harary 1962; Skiena 1990, p. 179; West 2000, p. 151).Harary graphs are implemented in the Wolfram Language as HararyGraph[k, n].When or is even, is a circulant graph. is the complete graph (Skiena 1990, p. 180).
The path graph is a tree with two nodes of vertex degree 1, and the other nodes of vertex degree 2. A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line (Gross and Yellen 2006, p. 18).The path graph of length is implemented in the Wolfram Language as PathGraph[Range[n]], and precomputed properties of path graphs are available as GraphData["Path", n]. (Note that the Wolfram Language believes cycle graphs to be path graph, a convention that seems neither standard nor useful.)The path graph is known as the singleton graph and is equivalent to the complete graph and the star graph . is isomorphic to the complete bipartite graph and to .Path graphs are graceful.The path graph has chromatic polynomial, independence polynomial, matching polynomial, and reliability polynomial given by(1)(2)(3)(4)where . These have recurrence equations(5)(6)(7)(8)The line graph of..
A two-dimensional grid graph, also known as a rectangular grid graph or two-dimensional lattice graph (e.g., Acharya and Gill 1981), is an lattice graph that is the graph Cartesian product of path graphs on and vertices. The grid graph is sometimes denoted (e.g., Acharya and Gill 1981).Unfortunately, the convention on which index corresponds to width and which to height remains murky. Some authors (e.g., Acharya and Gill 1981) use the same height by width convention applied to matrix dimensioning (which also corresponds to the order in which measurements of a painting on canvas are expressed). The Wolfram Language implementation GridGraph[m, n, ...] also adopts this ordering, returning an embedding in which corresponds to the height and the width. Other sources adopt the width by height convention used to measure paper, room dimensions, and windows (e.g., 8 1/2 inch by 11 inch paper is 8 1/2 inches wide and 11 inches high). Therefore, depending..
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.