Gallery of named graphs

From Infogalactic: the planetary knowledge core
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

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

  • Complete graph K4.svg

    K_4

  • K_5

  • K_6

  • K_7

  • Complete graph K8.svg

    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.

  • Biclique K 2 3.svg

    K_{2,3}

  • Biclique K 2 4.svg

    K_{2,4}

  • Biclique K 3 4.svg

    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

  • Circle graph C4.svg

    C_4

  • Circle graph C5.svg

    C_5

  • Undirected 6 cycle.svg

    C_6

Friendship graphs

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

File:Friendship graphs.svg
The friendship graphs F2, F3 and F4.

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.

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.

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

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_4 – W_9.

References

  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. ↑ Lua error in package.lua at line 80: module 'strict' not found.
Retrieved from "https://infogalactic.com/w/index.php?title=Gallery_of_named_graphs&oldid=682467923"