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).
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 -hypercube graph, also called the -cube graph and commonly denoted or , is the graph whose vertices are the symbols , ..., where or 1 and two vertices are adjacent iff the symbols differ in exactly one coordinate.The graph of the -hypercube is given by the graph Cartesian product of path graphs . The -hypercube graph is also isomorphic to the Hasse diagram for the Boolean algebra on elements.The above figures show orthographic projections of some small -hypercube graphs using the first two of each vertex's set of coordinates. Note that above is a projection of the usual cube looking along a space diagonal so that the top and bottom vertices coincide, and hence only seven of the cube's eight vertices are visible. In addition, three of the central edges connect to the upper vertex, while the other three connect to the lower vertex.Hypercube graphs may be computed in the Wolfram Language using the command HypercubeGraph[n], and precomputed properties..
The Desargues graph is the cubic symmetric graph on 20 vertices and 30 edges illustrated above in several embeddings. It is isomorphic to the generalized Petersen graph and to the bipartite Kneser graph . It is the incidence graph of the Desargues configuration. It can be represented in LCF notation as (Frucht 1976). It can also be constructed as the graph expansion of with steps 1 and 3, where is a path graph. It is distance-transitive and distance-regular graph and has intersection array .The Desargues graph is one of three cubic graphs on 20 nodes with smallest possible graph crossing number of 6 (the others being two unnamed graphs denoted CNG 6B and CNG 6C by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Desargues is an integral graph with graph spectrum . It is cospectral with another nonisomorphic graph (Haemers and Spence 1995, van Dam and Haemers 2003).It is also a unit-distance..
The -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 Heawood graph is a cubic graph on 14 vertices and 21 edges which is the unique (3,6)-cage graph. It is also a Moore graph. The Heawood graph is also the generalized hexagon , and its line graph is the generalized hexagon . The Heawood graph is illustrated above in a number of embeddings.It has graph diameter 3, graph radius 3, and girth 6. It is cubic symmetric, nonplanar, Hamiltonian, and can be represented in LCF notation as .It has chromatic number 2 and chromaticpolynomialIts graph spectrum is .It is 4-transitive, but not 5-transitive (Harary 1994, p. 173).The Heawood graph is one of eight cubic graphs on 14 nodes with smallest possible graph crossing number of 3 (another being the generalized Petersen graph ), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Heawood graph corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line incidence..
A bicubic graph is a bipartite cubicgraph.Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture), but a number of nonhamiltonian bicubic graphs have subsequently been discovered.The numbers of simple bicubic graphs on , 4, ... nodes are 0, 0, 1, 1, 2, 5, 13, 38, 149, ... (OEIS A006823), the first few of which are illustrated above.The following table summarizes some named bicubic graphs.graph utility graph6cubical graph8Franklin graph12Heawood graph14Möbius-Kantor graph16Pappus graph18Desargues graph20truncated octahedral graph24Levi graph30Dyck graph32great rhombicuboctahedral graph48Gray graph54Balaban 10-cage70Foster graph90great rhombicosidodecahedral graph120Tutte 12-cage126
The Franklin graph is the 12-vertex cubic graph shown above whose embedding on the Klein bottle divides it into regions having a minimal coloring using six colors, thus providing the sole counterexample to the Heawood conjecture. The graph is implemented in the Wolfram Language as GraphData["FranklinGraph"].It is the 6-crossed prism graph.The minimal coloring of the Franklin graph is illustrated above.The Franklin graph is nonplanar but Hamiltonian. It has LCF notations and .The graph spectrum of the Franklin graph is .
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 gear graph, also sometimes known as a bipartite wheel graph (Brandstädt et al. 1987), is a wheel graph with a graph vertex added between each pair of adjacent graph vertices of the outer cycle (Gallian 2018). The gear graph has nodes and edges.Gear graphs are unit-distance and matchstickgraphs, as illustrated in the embeddings shown above.Attractive derived unit-distance graph are produced by taking the vertex sets from the matchstick embeddings and connecting all pairs of vertices separate by a unit distance for , 6, 12, and 18, illustrated above, with the case corresponding to the wheel graph .Ma and Feng (1984) proved that all gear graphs are graceful, and Liu (1996) showed that if two or more vertices are inserted between every pair of vertices of the outer cycle of the wheel, the resulting graph is also graceful (Gallian 2018).Precomputed properties of gear graphs are given in the Wolfram Language by GraphData["Gear",..
An -firecracker is a graph obtained by the concatenation of -stars by linking one leaf from each (Chen et al. 1997, Gallian 2007).Firecracker graphs are graceful (Chen et al.1997, Gallian 2018).Precomputed properties of firecrackers are implemented in the Wolfram Language as GraphData["Firecracker", n, k].
The cubical graph is the Platonic graph corresponding to the connectivity of the cube. It is isomorphic to the generalized Petersen graph , bipartite Kneser graph , 4-crossed prism graph, crown graph , grid graph , hypercube graph , and prism graph . It is illustrated above in a number of embeddings (e.g., Knuth 2008, p. 14).It has 12 distinct (directed) Hamiltonian cycles, corresponding to the unique order-4 LCF notation .It is a unit-distance graph, as shown above in a unit-distance drawing (Harborth and Möller 1994).The minimal planar integral drawings of the cubical graph, illustrated above, has maximum edge length of 2 (Harborth et al. 1987). They are also graceful (Gardner 1983, pp. 158 and 163-164). can be constructed as the graph expansion of with steps 1 and 1, where is a path graph. Excising an edge of the cubical graph gives the prism graph .The cubical graph has 8 nodes, 12 edges, vertex connectivity 3, edge connectivity..
The -ladder graph can be defined as , where is a path graph (Hosoya and Harary 1993; Noy and Ribó 2004, Fig. 1). It is therefore equivalent to the grid graph. The ladder graph is named for its resemblance to a ladder consisting of two rails and rungs between them (though starting immediately at the bottom and finishing at the top with no offset).Hosoya and Harary (1993) also use the term "ladder graph" for the graph Cartesian product , where is the complete graph on two nodes and is the cycle graph on nodes. This class of graph is however more commonly known as a prism graph.Ball and Coxeter (1987, pp. 277-278) use the term "ladder graph" to refer to the graph known in this work as the ladder rung graph.The ladder graph is graceful (Maheo 1980).The chromatic polynomial, independence polynomial, and reliability polynomial of the ladder graph are given by(1)(2)(3)where . Recurrence equations for the chromatic..
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 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.
"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)
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..