Gallery of named graphs
Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.
Individual graphs
-
Balaban 10-cage alternative drawing.svg
-
Balaban 11-cage.svg
-
Bidiakis cube.svg
-
Brinkmann graph LS.svg
-
Bull graph.circo.svg
-
Chvatal graph.draw.svg
-
Dürer graph.svg
-
Ellingham-Horton 54-graph.svg
-
Ellingham-Horton 78-graph.svg
-
Errera graph.svg
-
Franklin graph.svg
-
Frucht planar Lombardi.svg
-
Groetzsch-graph.svg
-
Harries graph alternative drawing.svg
-
Harries-wong graph.svg
-
Herschel graph no col.svg
-
Hoffman graph.svg
-
Horton graph.svg
-
Kittell graph.svg
-
Markström-Graph.svg
-
Meredith graph.svg
-
Moser spindle.svg
-
Sousselier graph.svg
-
Poussin graph.svg
-
Robertson graph.svg
-
Sylvester graph.svg
-
Tutte fragment.svg
-
Tutte graph.svg
-
Young-Fibonacci.svg
-
Wagner graph ham.svg
-
Wells graph.svg
-
Wiener-Araya.svg
Highly symmetric graphs
Strongly regular graphs
The strongly regular graph on v vertices and rank k is usually denoted srg(v,k,λ,μ).
-
Cameron graph.svg
-
Hall janko graph.svg
-
Hoffman singleton graph circle2.gif
-
Higman Sims Graph.svg
-
Paley graph of order 13
-
Schläfli graph.svg
-
Brouwer Haemers graph.svg
-
Local mclaughlin graph.svg
-
Gewirtz graph embeddings.svg
Symmetric graphs
A symmetric graph is one in which there is a symmetry (graph automorphism) taking any ordered pair of adjacent vertices to any other ordered pair; the Foster census lists all small symmetric 3-regular graphs. Every strongly regular graph is symmetric, but not vice versa.
-
Möbius–Kantor unit distance.svg
-
Pappus graph.svg
-
DesarguesGraph.svg
-
Coxeter graph.svg
-
Dyck graph.svg
-
Klein graph.svg
-
Foster graph.svg
-
Biggs-Smith graph.svg
-
Rado graph.svg
The Rado graph
Semi-symmetric graphs
-
Gray graph hamiltonian.svg
-
Ljubljana graph hamiltonian.svg
-
Tutte 12-cage.svg
Graph families
Complete graphs
The complete graph on vertices is often called the -clique and usually denoted , from German komplett.[1]
-
Complete graph K4.svg
-
Complete graph K8.svg
Complete bipartite graphs
The complete bipartite graph is usually denoted . For see the section on star graphs. The graph equals the 4-cycle (the square) introduced below.
-
Biclique K 2 3.svg
-
, the utility graph
-
Biclique K 2 4.svg
-
Biclique K 3 4.svg
Cycles
The cycle graph on vertices is called the n-cycle and usually denoted . It is also called a cyclic graph, a polygon or the n-gon. Special cases are the triangle , the square , and then several with Greek naming pentagon , hexagon , etc.
-
Circle graph C4.svg
-
Circle graph C5.svg
-
Undirected 6 cycle.svg
Friendship graphs
The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[2]
Fullerene graphs
In graph theory, the term fullerene refers to any 3-regular, planar graph with all faces of size 5 or 6 (including the external face). It follows from Euler's polyhedron formula, V – E + F = 2 (where V, E, F indicate the number of vertices, edges, and faces), that there are exactly 12 pentagons in a fullerene and V/2–10 hexagons. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.
-
20-fullerene (dodecahedral graph)
-
Graph of 24-fullerene w-nodes.svg
24-fullerene (Hexagonal truncated trapezohedron graph)
-
60-fullerene (truncated icosahedral graph)
An algorithm to generate all the non-isomorphic fullerens with a given number of hexagonal faces has been developed by G. Brinkmann and A. Dress.[3] G. Brinkmann also provided a freely available implementation, called fullgen.
Platonic solids
The complete graph on four vertices forms the skeleton of the tetrahedron, and more generally the complete graphs form skeletons of simplices. The hypercube graphs are also skeletons of higher-dimensional regular polytopes.
-
Cube
, -
Octahedral graph.circo.svg
Truncated solids
-
Truncated cubical graph.neato.svg
Snarks
A snark is a bridgeless cubic graph that requires four colors in any proper edge coloring. The smallest snark is the Petersen graph, already listed above.
-
First Blanusa snark.svg
-
Second Blanusa snark.svg
-
Double-star snark.svg
-
Flower snarkv.svg
-
Loupekine 1.svg
Loupekine snark (first)
-
Loupekine 2.svg
Loupekine snark (second)
-
Szekeres-snark.svg
-
Tietze's graph.svg
-
Watkins snark.svg
Star
A star Sk is the complete bipartite graph K1,k. The star S3 is called the claw graph.
Wheel graphs
The wheel graph Wn is a graph on n vertices constructed by connecting a single vertex to every vertex in an (n − 1)-cycle.
References
- ↑ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
- ↑ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [1].
- ↑ Lua error in package.lua at line 80: module 'strict' not found.