List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see Category: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

Highly symmetric graphs

Strongly regular graphs

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

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.

Semi-symmetric graphs

Graph families

Complete graphs

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

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

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

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

Fullerene graphs

In graph theory, a fullerene is any polyhedral 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

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

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.

Star

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

Wheel graphs

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.

Other graphs

This partial list contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own.

Gear

A gear graph, denoted G_n, is a graph obtained by inserting an extra vertex between each pair of adjacent vertices on the perimeter of a wheel graph W_n. Thus, G_n has 2n+1 vertices and 3n edges.^[4] Gear graphs are examples of squaregraphs, and play a key role in the forbidden graph characterization of squaregraphs.^[5] Gear graphs are also known as cogwheels and bipartite wheels.

Helm

A helm graph, denoted H_n, is a graph obtained by attaching a single edge and node to each node of the outer circuit of a wheel graph W_n.^[6]^[7]

Lobster

A lobster graph is a tree in which all the vertices are within distance 2 of a central path.^[8]^[9] Compare caterpillar.

Web

The web graph W_n,r is a graph consisting of r concentric copies of the cycle graph C_n, with corresponding vertices connected by "spokes". Thus W_n,1 is the same graph as C_n, and W_n,2 is a prism.

A web graph has also been defined as a prism graph Y_{n+1, 3}, with the edges of the outer cycle removed.^[7]^[10]

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] 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.
^ Weisstein, Eric W. "Gear graph". MathWorld.
^ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID 10788524
^ Weisstein, Eric W. "Helm graph". MathWorld.
^ ^a ^b "Archived copy" (PDF). Archived from the original (PDF) on 2012-01-31. Retrieved 2008-08-16.{{cite web}}: CS1 maint: archived copy as title (link)
^ "Google Discussiegroepen". Retrieved 2014-02-05.
^ Weisstein, Eric W. Graph.html "Lobster Graph". MathWorld. {{cite web}}: Check |url= value (help)
^ Weisstein, Eric W. "Web graph". MathWorld.

[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.

[4] Weisstein, Eric W. "Gear graph". MathWorld.

[5] Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID 10788524

[6] Weisstein, Eric W. "Helm graph". MathWorld.

[combinatorics.org-7] "Archived copy" (PDF). Archived from the original (PDF) on 2012-01-31. Retrieved 2008-08-16.{{cite web}}: CS1 maint: archived copy as title (link)

[8] "Google Discussiegroepen". Retrieved 2014-02-05.

[9] Weisstein, Eric W. Graph.html "Lobster Graph". MathWorld. {{cite web}}: Check |url= value (help)

[10] Weisstein, Eric W. "Web graph". MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]