List of graphs

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

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 .

Caterpillar

A caterpillar graph, or caterpillar tree, is a tree such that if all leaf vertices and their incident edges are removed, the remainder of the graph forms a path. In other words, all the vertices of a caterpillar are within distance 1 of a central path.

Alternatively,A caterpillar is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree >=3 are surrounded by at most two nodes of degree two or greater. [mathworld|urlname=Caterpillar|title=Caterpillar] Compare "lobster".

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 2"n"+1 vertices and 3"n" edges. [mathworld|urlname=GearGraph|title=Gear graph]

Grid

A grid graph is a unit distance graph corresponding to the square lattice, so that it is isomorphic to the graph having a vertex corresponding to every pair of integers ("a", "b"), and an edge connecting ("a", "b") to ("a"+1, "b") and ("a", "b"+1). The finite grid graph "G_m,n" is an "m"×"n" rectangular graph isomorphic to the one obtained by restricting the ordered pairs to the range 0 ≤ "a" < "m", 0 ≤ "b" < "n". Grid graphs can be obtained as the Cartesian product of two paths: "G"_"m","n" = "P"_"m" × "P"_"n". Every grid graph is a median graph. [mathworld|urlname=GridGraph|title=Grid graph]

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". [mathworld|urlname=HelmGraph|title=Helm graph] [ [http://www.combinatorics.org/Surveys/ds6.pdf Joseph A. Gallian, "A Dynamic Survey of Graph Labeling"] ]

Ladder

A ladder graph can be obtained as the Cartesian product of two paths, one of which has only one edge: "G"_"m","1" = "P"_"m" × "P"_"1". [MathWorld|title=Ladder Graph|urlname=LadderGraph] Adding two more crossed edges connecting the four degree-two vertices of a ladder graph produces a cubic graph, the Möbius ladder.

Lobster

A lobster graph is a graph in which all the vertices are within distance 2 of a central path. [http://groups.google.com/groups?selm=[e-mail]] 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. [mathworld|urlname=WebGraph|title=Web graph] [ [http://www.combinatorics.org/Surveys/ds6.pdf Joseph A. Gallian, "A Dynamic Survey of Graph Labeling"] ]

References