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[edit]

Highly symmetric graphs[edit]

Strongly regular graphs[edit]

The strongly regular graph on v vertices and rank k is usually denoted srg(v,k,λ,μ).

Symmetric graphs[edit]

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.

Semi-symmetric graphs[edit]

Graph families[edit]

Complete graphs[edit]

The complete graph on $n$ vertices is often called the $n$ -clique and usually denoted $K_{n}$ , from German komplett.^[1]

$K_{1}$
$K_{2}$
$K_{3}$
$K_{4}$
$K_{5}$
$K_{6}$
$K_{7}$
$K_{8}$

Complete bipartite graphs[edit]

The complete bipartite graph is usually denoted $K_{n,m}$ . For $n=1$ see the section on star graphs. The graph $K_{2,2}$ equals the 4-cycle $C_{4}$ (the square) introduced below.

$K_{2,3}$
$K_{3,3}$ , the utility graph
$K_{2,4}$
$K_{3,4}$

Cycles[edit]

The cycle graph on $n$ vertices is called the n-cycle and usually denoted $C_{n}$ . It is also called a cyclic graph, a polygon or the n-gon. Special cases are the triangle $C_{3}$ , the square $C_{4}$ , and then several with Greek naming pentagon $C_{5}$ , hexagon $C_{6}$ , etc.

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

Friendship graphs[edit]

The friendship graph F_n can be constructed by joining n copies of the cycle graph C₃ with a common vertex.^[2]

The friendship graphs F₂, F₃ and F₄.

Fullerene graphs[edit]

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 h = V/2 – 10 hexagons. Therefore V = 20 + 2h; E = 30 + 3h. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.

20-fullerene (dodecahedral graph)
24-fullerene (Hexagonal truncated trapezohedron graph)
26-fullerene graph
60-fullerene (truncated icosahedral graph)
70-fullerene

An algorithm to generate all the non-isomorphic fullerenes 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[edit]

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
$n=8$ , $m=12$
Octahedron
$n=6$ , $m=12$
Dodecahedron
$n=20$ , $m=30$
Icosahedron
$n=12$ , $m=30$

Truncated solids[edit]

Snarks[edit]

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.

Star[edit]

A star S_k is the complete bipartite graph K_1,k. The star S₃ is called the claw graph.

The star graphs S₃, S₄, S₅ and S₆.

Wheel graphs[edit]

The wheel graph W_n is a graph on n vertices constructed by connecting a single vertex to every vertex in an (n − 1)-cycle.

Wheels

W_{4}

–

W_{9}

.

References[edit]

^ 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] Archived 2012-01-31 at the Wayback Machine.
^ Brinkmann, Gunnar; Dress, Andreas W.M (1997). "A Constructive Enumeration of Fullerenes". Journal of Algorithms. 23 (2): 345–358. doi:10.1006/jagm.1996.0806. MR 1441972.

[1] David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

[2] Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [1] Archived 2012-01-31 at the Wayback Machine.

[3] Brinkmann, Gunnar; Dress, Andreas W.M (1997). "A Constructive Enumeration of Fullerenes". Journal of Algorithms. 23 (2): 345–358. doi:10.1006/jagm.1996.0806. MR 1441972.

[1]

[2]

[3]