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