Tag

Sort by:

King graph

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..

Queen graph

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..

Barnette's conjecture

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.

Snark

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,..

Banana tree

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].

Triangular snake graph

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 .

Kayak paddle graph

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).

Torus grid graph

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..

Butterfly 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 )...

Hypercube graph

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..

Shrikhande graph

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..

Cocktail party graph

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..

Cactus graph

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)...

Centipede graph

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

Spider graph

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.

Nonhamiltonian bicubic graph

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..

Meredith graph

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.

Bicubic graph

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

Tietze's graph

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.

Kittell 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.

Soifer graph

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"].

Royle graphs

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.

Chvátal graph

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 ...

Moser spindle

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).

Bipartite graph

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..

Caveman graph

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].

Helm graph

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)

Pan graph

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",..

Gear graph

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",..

Octahedral graph

"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..

Firecracker graph

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].

Tetrahedral graph

"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..

Dodecahedral graph

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...

Tadpole graph

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).

Möbius ladder

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 ...

Cubical 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..

Ladder graph

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..

Complete bipartite graph

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..

Icosahedral graph

The icosahedral graph is the Platonic graph whose nodes have the connectivity of the icosahedron, illustrated above in a number of embeddings. The icosahedral graph has 12 vertices and 30 edges.Since the icosahedral graph is regular and Hamiltonian, it has a generalized LCF notation. In fact, there are two distinct generalized LCF notations of order 6-- and --8 of order 2, and 17 of order 1, illustrated above.It is implemented in the Wolfram Languageas GraphData["IcosahedralGraph"].It is a distance-regular graph with intersection array , and therefore also a Taylor graph. It is also distance-transitive.There are two minimal integral drawings of the icosahedral graph, illustrated above, all with maximum edge length of 8 (Harborth and Möller 1994). It is also graceful (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35), with five fundamentally different labelings (Gardner 1983, p. 164).The..

H 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)

Apollonian network

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..

Rook graph

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..

Cycle graph

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..

Turán graph

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..

Complete graph

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..

Circulant graph

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..

Petersen graph

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..

Path graph

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..

Generalized petersen graph

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,..

Check the price
for your project
we accept
Money back
guarantee
100% quality