Gallery of named graphs

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

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.

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.

Friendship graphs[edit]

The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[2]

The friendship graphs F2, F3 and F4.

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 V/2–10 hexagons. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.

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

Truncated solids[edit]

Snarks[edit]

A snark is a bridgeless cubic graph that requires four colors in any edge coloring. The smallest snark is the Petersen graph, already listed above.

Star[edit]

A star Sk is the complete bipartite graph K1,k. The star S3 is called the claw graph.

The star graphs S3, S4, S5 and S6.

Wheel graphs[edit]

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

Wheels W_4W_9.

References[edit]

  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].
  3. ^ Journal of Algorithms 23 (2): 345–358. 1997. doi:10.1006/jagm.1996.0806. MR 1441972.