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,..
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.
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].
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 .
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.
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).
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 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)
A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form(1)where is the partition function P and is the floor function. A generating function for is given by(2)(3)(4)where is a q-Pochhammer symbol.Not all spiders are caterpillar graphs, norare all spiders lobster graphs.
The (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 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)
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).
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..
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..
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).
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..
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.
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..
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..