Graph (discrete mathematics): Difference between revisions

Revision as of 04:52, 27 June 2006

Revision as of 05:04, 27 June 2006

Line 45:

A '''simple graph''' is always understood to mean a "graph" which contains no loops or multiple edges. However, the unqualified term "graph" might allow or disallow loops and multiple edges in the literature, according to the preferences of the author and the requirements of the particular topic.

The term "[[multigraph]]" is used to indicate that multiple edges (and sometimes loops) are allowed. Where graphs are defined so as to ''allow'' loops and multiple edges, a multigraph is often defined to mean a graph without loops,<ref> For example, see Balakrishnan, p. 1, and Gross (2003), p. 4, and Zwillinger, p. 220.</ref> however, where graphs are defined so as to ''disallow'' loops and mutiple edges, the term is often defined to mean a "graph" which can have loops or multiple edges.<ref>For example, see. Bollobas, p. 7 and Diestel, p. 25.</ref>

Sometimes the term "[[pseudograph]]" is used to indicate that both multiple edges and loops are allowed.<ref>Gross (2005), p. 3, and Zwillinger, p. 220.</ref> In exceptional situations it is even necessary to have edges with only one end, called '''halfedges''', or no ends ('''loose edges'''); see for example [[signed graph]]s.

==Properties of graphs==