Two nonisomorphic graphs can share the same graph spectrum, i.e., have the same eigenvalues of their adjacency matrices. Such graphs are called cospectral. For example, the graph union and star graph , illustrated above, both have spectrum (Skiena 1990, p. 85). This is the smallest pair of simple graphs that are cospectral. Determining which graphs are uniquely determined by their spectra is in general a very hard problem.Only a small fraction of graphs are known to be so determined, but it is conceivablethat almost all graphs have this property (van Dam and Haemers 2002).In the Wolfram Language, graphs knownto be determined by their spectra are identified as GraphData["DeterminedBySpectrum"].The numbers of simple graphs on , 2, ... nodes that are determined by spectrum are 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925), while the corresponding numbers not determined by spectrum are 0, 0, 0, 0, 2, 10, 110, 1722,..
"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 )...
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.
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).
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",..
"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..
"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..
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...
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..
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..