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 snark is a connected bridgeless cubic graph (i.e., a biconnected cubic graph) with edge chromatic number of four. (By Vizing's theorem, the edge chromatic number of every cubic graph is either three or four, so a snark corresponds to the special case of four.) Snarks are therefore class 2 graphs.In order to avoid trivial cases, snarks are commonly restricted to be connected (so that the graph union of two Petersen graphs is excluded), have girth 5 or more and not to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial (Read and Wilson 1998, p. 263).Snarks that are trivial in the above senses are sometimes called "reducible" snarks. A number of reducible snarks are illustrated above.The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graph graph minors. This conjecture was proven in 2001 by Robertson, Sanders, Seymour, and Thomas,..
An -banana tree, as defined by Chen et al. (1997), is a graph obtained by connecting one leaf of each of copies of an -star graph with a single root vertex that is distinct from all the stars.Banana trees are graceful (Sethuraman and J. Jesintha2009, Gallian 2018).The -banana tree has rank polynomialPrecomputed properties of a number of banana trees is implemented in the Wolfram Language as GraphData["BananaTree", n, k].
The flower snarks are a family of snarks discovered by Isaacs (1975) and denoted . is Tietze's graph, which is a "reducible snark" since it contains a cycle of length less than 5. is illustrated above in two embeddings, the second of which appears in Scheinerman and Ullman (2011, p. 96) as an example of a graph with edge chromatic number and fractional edge chromatic number (4 and 3, respectively) both integers but not equal. is maximally nonhamiltonian for odd (Clark and Entringer 1983).
The -centipede graph, -centipede tree, or simply "-centipede," is the tree on nodes obtained by joining the bottoms of copies of the path graph laid in a row with edges. It is therefore isomorphic to the -firecracker graph, with special cases summarized in the table below.graph1path graph 2path graph 3E graphThe rank polynomial of the centipede is given by
A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form(1)where is the partition function P and is the floor function. A generating function for is given by(2)(3)(4)where is a q-Pochhammer symbol.Not all spiders are caterpillar graphs, norare all spiders lobster graphs.
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.
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
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..
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)
An -firecracker is a graph obtained by the concatenation of -stars by linking one leaf from each (Chen et al. 1997, Gallian 2007).Firecracker graphs are graceful (Chen et al.1997, Gallian 2018).Precomputed properties of firecrackers are implemented in the Wolfram Language as GraphData["Firecracker", n, k].
The -tadpole graph, also called a dragon graph (Truszczyński 1984) or kite graph (Kim and Park 2006), is the graph obtained by joining a cycle graph to a path graph with a bridge.The -tadpole graph is sometimes known as the -pan graph. The particular cases of the - and -tadpole graphs are also known as the paw graph and banner graph, respectively (ISGCI).Precomputed properties of tadpole graphs are available in the Wolfram Language as GraphData["Tadpole", m, n].Koh et al. (1980) showed that -tadpole graphs are graceful for , 1, or 3 (mod 4) and conjectured that all tadpole graphs are graceful (Gallian 2018). Guo (1994) apparently completed the proof by filling in the missing case in the process of showing that tadpoles are graceful when or 2 (mod 4) (Gallian 2018).
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.