Gallery of named graphs

From Wikipedia, the free encyclopedia

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.

Contents 1 Individual graphs 2 Graph families 2.1 Strongly regular graph 2.2 Complete graphs 2.3 Complete bipartite graphs 2.4 Platonic solids 2.5 Cycles 2.6 Star 2.7 Wheel 2.8 Fullerene graphs

[edit] Individual graphs

Chvátal graph	Desargues graph	Desargues graph (colored)	Flower snark
Folkman graph	Foster graph	Foster graph (colored)	Gray graph
Grötzsch graph	Heawood graph	Möbius–Kantor graph	Pappus graph
Pappus graph (colored)	Szekeres snark	Tutte eight-cage

[edit] Graph families

[edit] Strongly regular graph

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

Clebsch graph	Petersen graph	Hall–Janko graph	Hoffman–Singleton graph
Higman–Sims graph	Paley graph	Shrikhande graph

[edit] Complete graphs

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

K1	K2	K3	K4
K5	K6	K7	K8

[edit] Complete bipartite graphs

The complete bipartite graph is usually denoted K_n,m. The graph K_2,2 equals the 4-cycle C₄ (the square) introduced below.

Claw K3,1

K3,2

K3,3

[edit] 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 n = 8, m = 12

Octahedron n = 6, m = 12

Dodecahedron n = 20, m = 30

Icosahedron n = 12, m = 30

[edit] Cycles

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₃, the square C₄, and then several with greek naming pentagon C₅, hexagon C₆, etc.

C3

C4

C5

C6

[edit] Star

A star S_k is the complete bipartite graph K_1,k.

S7

[edit] Wheel

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 W4 – W9

[edit] 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)	24-fullerene (Hexagonal truncated trapezohedron graph)	26-fullerene	60-fullerene (truncated icosahedral graph)
70-fullerene