Multiple edges

Multiple edges joining two vertices.

In graph theory, multiple edges (also called parallel edges or a multi-edge), are two or more edges that are incident to the same two vertices. A simple graph has no multiple edges.

Depending on the context, a graph may be defined so as to either allow or disallow the presence of multiple edges (often in concert with allowing or disallowing loops):

Multiple edges are, for example, useful in the consideration of electrical networks, from a graph theoretical point of view.[3] Additionally, they constitute the core differentiating feature of multidimensional networks.

A planar graph remains planar if an edge is added between two vertices already joined by an edge; thus, adding multiple edges preserves planarity.[4]

A dipole graph is a graph with two vertices, in which all edges are parallel to each other.

Notes

  1. For example, see Balakrishnan, p. 1, and Gross (2003), p. 4, Zwillinger, p. 220.
  2. For example, see Bollobás, p. 7; Diestel, p. 28; Harary, p. 10.
  3. Bollobás, pp. 3940.
  4. Gross (1998), p. 308.

References

This article is issued from Wikipedia - version of the Monday, February 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.