nLab
directed graph

Contents

Terminology

The term directed graph is used in both graph theory and category theory and the precise definition varies depending on the particular reference under consideration even within the same field.

In graph theory, directed graph or digraph usually means a simple directed graph, and category theory, directed graph or digraph usually means a quiver, which may have multiple edges and loops; the basic difference here is that (according to one widespread convention), in a large part of combinatorics the word digraph implies that there are neither loops nor parallel arcs (while directed cycles of length 2 are allowed in a digraph; cf. e.g. Section 1.2).

From a category-theoretic point of view, it is not superfluous to state the obvious fact that this is somewhat orthogonal to how the underlying quiver of a category looks like: this always has a loop at each vertex, and, usually, many parallel arcs. In particular, the underlying quiver of a category is never a digraph (in the sense of some books ).

A generous disregard to the issue of allowing loops or not, and sometimes even to allowing parallel arcs, is common in the literatur. In a sense, because of the additional information given by directions, digraph theory has more technical terms than graph theory.

We here list a few, but only in so far as they are fundamental and potentially useful in category theory. 1

References

  • Gregory Gutin?, Jørgen Bang-Jensen?: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Second Edition (2009)
  • Michael Johnson?: Pasting Diagrams in nn-Categories with Applications to Coherence Theorems and Categories of Paths, Doctoral Thesis, University of Sydney, 1987
  • Michael Johnson?: The Combinatorics of nn-Categorical Pasting, Journal of Pure and Applied Algebra 62 (1989)


  1. One example of a use of digraph theory sensu stricto in category theory is giving a rigorous justification of the notational practice called pasting schemes, carried out since the 1980s (cf. e.g. Johnson87, Johnson89 ), where parallel arcs or loops are rare, and sometimes expressly forbidden.

Revised on July 22, 2017 14:51:48 by Peter Heinig (2003:58:aa1f:f900:8285:32a9:47b1:f47c)