A simplex, sometimes called a hypertetrahedron (Buekenhout and Parker 1998), is the generalization of a tetrahedral region of space to dimensions. The boundary of a -simplex has 0-faces (polytope vertices), 1-faces (polytope edges), and -faces, where is a binomial coefficient. An -dimensional simplex can be denoted using the Schläfli symbol . The simplex is so-named because it represents the simplest possible polytope in any given space.The content (i.e., hypervolume) of a simplex can be computedusing the Cayley-Menger determinant.In one dimension, the simplex is the line segment . In two dimensions, the simplex is the convex hull of the equilateral triangle. In three dimensions, the simplex is the convex hull of the tetrahedron. The simplex in four dimensions (the pentatope) is a regular tetrahedron in which a point along the fourth dimension through the center of is chosen so that . The regular simplex in dimensions with is denoted..
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)...
An integral graph is defined as a graph whose graph spectrum consists entirely of integers. The notion was first introduced by Harary and Schwenk (1974). The numbers of simple integral graphs on , 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small .The numbers of connected simple integral graphs on , 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small .The following table lists common graph classes and the their members which are integral.graphintegral for of the formantiprism graph3complete graph allcycle graph 2, 3, 4, 6empty graphallprism graph3, 4, 6star graph wheel graph 4The following table lists some special named graphs that are integral and gives their spectra.graphgraph spectrum16-cell24-cellClebsch graphcubical graphcuboctahedral graphDesargues graphHall-Janko graphHoffman graphHoffman-Singleton graphLevi graphM22 graphMcLaughlin..
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 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..
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..
A wheel graph of order , sometimes simply called an -wheel (Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78), is a graph that contains a cycle of order , and for which every graph vertex in the cycle is connected to one other graph vertex (which is known as the hub). The edges of a wheel which include the hub are called spokes (Skiena 1990, p. 146). The wheel can be defined as the graph , where is the singleton graph and is the cycle graph. Note that there are two conventions for the indexing for wheel graphs, with some authors (e.g., Gallian 2007), adopting the convention that denotes the wheel graph on nodes.The tetrahedral graph (i.e., ) is isomorphic to , and is isomorphic to the complete tripartite graph . In general, the -wheel graph is the skeleton of an -pyramid. is one of the two graphs obtained by removing two edges from the pentatope graph , the other being the house X graph.Wheel graphs are graceful (Frucht..
The star graph of order , sometimes simply known as an "-star" (Harary 1994, pp. 17-18; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 23), is a tree on nodes with one node having vertex degree and the other having vertex degree 1. The star graph is therefore isomorphic to the complete bipartite graph (Skiena 1990, p. 146).Note that there are two conventions for the indexing for star graphs, with some authors (e.g., Gallian 2007), adopting the convention that denotes the star graph on nodes. is isomorphic to "the" claw graph. A star graph is sometimes termed a "claw" (Hoffman 1960) or a "cherry" (Erdős and Rényi 1963; Harary 1994, p. 17).Star graphs are always graceful. Star graphs can be constructed in the Wolfram Language using StarGraph[n]. Precomputed properties of star graphs are available via GraphData["Star", n].The chromatic..
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..
The large Witt graph, also called the octad graph (Brouwer) or Witt graph (DistanceRegular.org), is the graph whose vertices are the 759 blocks of a Steiner system in which two blocks are adjacent whenever they are disjoint (Brouwer et al. 1989, p. 366).Perhaps the simplest construction is by selecting the 759 codewords of weight 8 of the extended binary Golay code and joining two words when they have disjoint support (i.e., if the codeword vectors are orthogonal).It is a distance-regular graph with intersection array and is also distance-transitive. It is an integral graph with graph spectrum . Its automorphism group has order , where is the largest Mathieu group. Its chromatic number is apparently unknown.The large Witt graph is implemented in the WolframLanguage as GraphData["LargeWittGraph"]...
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..
The doubly truncated Witt graph is the graph on 330 vertices related to a 3- design (Brouwer et al. 1989, p. 367). The doubly truncated Witt graph can be constructed by removing all vectors of the large Witt design containing any two arbitrarily chosen symbols. Consider the 759 vertices of the large Witt graph as words of weight 8 in extended binary Golay. Call the octads, and view them as sets of size 8. Pick one coordinate position. 253 octads have a 1 there, 506 octads have a 0 there. Pick a second coordinate position. Of the 506, there are 176 with a 1 there, and 330 with a 0. The induced subgraph from 759, or from 506 on this 330 gives the doubly truncated Witt graph (A. E. Brouwer, pers. comm., Jun. 8, 2009).It is an integral graph with graph spectrum , is weakly regular with parameters . It is also distance-transitive with intersection array . The order of its automorphism group is , where is a Mathieu group.This graph is implemented..
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..
"The" Sylvester graph is a quintic graph on 36 nodes and 90 edges that is the unique distance-regular graph with intersection array (Brouwer et al. 1989, §13.1.2; Brouwer and Haemers 1993). It is a subgraph of the Hoffman-Singleton graph obtainable by choosing any edge, then deleting the 14 vertices within distance 2 of that edge.It has graph diameter 3, girth 5, graph radius 3, is Hamiltonian, and nonplanar. It has chromatic number 4, edge connectivity 5, vertex connectivity 5, and edge chromatic number 5.It is an integral graph and has graph spectrum (Brouwer and Haemers 1993).The Sylvester graph of a configuration is the set of ordinarypoints and ordinary lines.