Multigraph

The term multigraph refers to a graph in which multiple edges between nodes are either permitted (Harary 1994, p. 10; Gross and Yellen 1999, p. 4) or required (Skiena 1990, p. 89, Pemmaraju and Skiena 2003, p. 198; Zwillinger 2003, p. 220). West (2000, p. xiv) recommends avoiding the term altogether on the grounds of this ambiguity.

Some references require that multigraphs possess no graph loops (Harary 1994, p. 10; Gross and Yellen 1999, p. 4; Zwillinger 2003, p. 220), some explicitly allow them (Hartsfield and Ringel 1994, p. 7; Cormen et al. 2001, p. 89), and yet others do not include any explicit allowance or disallowance (Skiena 1990, p. 89; Gross and Yellen 1999, p. 351; Pemmaraju and Skiena 2003, p. 198). Worse still, Tutte (1998, p. 2) uses the term "multigraph" to mean a graph containing either loops or multiple edges.

As a result of these many ambiguities, use of the term "multigraph" should be deprecated, or at the very least used with extreme caution.

REFERENCES

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; and Stein, C. Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001.

Grimaldi, R. P. Discrete and Combinatorial Mathematics: An Applied Introduction, 4th ed. Longman, 1998.

Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, 1999.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 10, 1994.

Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction, 2nd ed. San Diego, CA: Academic Press, 1994.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Tutte, W. T. Graph Theory as I Have Known It. Oxford, England: Oxford University Press, 1998.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Zwillinger, D. (Ed.). CRC Standard Mathematical Tables and Formulae, 31st ed. Boca Raton, FL: CRC Press, 2003.