Directed graphs
For category theorists, graphs are directed by default, but for graph theorists, “graph” usually means “undirected graph.” The theory of directed graphs is not as extensively developed as that of undirected graphs, although the literature is still quite large.
Major textbook and monograph references are:
- Bang-Jensen & Gutin, 2009, 2nd ed: Digraphs: Theory, algorithms, and applications (doi)
- Hell & Nesetril, 2004: Graphs and homomorphisms (doi)
- Not exclusively about digraphs, but takes digraphs as the basic notion and specializes to other classes (symmetric, reflexive, symmetric and reflexive) as appropriate
Directed spectral graph theory
Spectral graph theory mainly treats undirected graphs. Several generalizations of the Laplacian to directed graphs have been proposed, but as far as I know no definition is accepted as standard. Many authors simply symmetrize directed graphs and apply the undirected Laplacian (as, for example, in Jean Gallier’s lecture notes and slides).
- Chung, 2005: Laplacians and the Cheeger inequality for directed graphs (doi)
- Zhang & Li, 2012: Digraph Laplacian and the degree of asymmetry (doi)
- Veerman & Lyons, 2020: A primer on Laplacian dynamics in directed graphs
(doi, arxiv, pdf)
- “Many of the results we will discuss had earlier been ‘folklore’ results living largely outside the mathematics community”
- Synthesis of previous work:
Functional graphs
A functional graph is a directed graph where every vertex has out-degree 1. Equivalently, it is a simple directed graph whose edge relation is the graph of a function, hence the name.
- Maurer, 2013: Directed acyclic graphs, Definition D21
- Chapter in Gross et al, eds., 2013: Handbook of graph theory, 2nd ed.
- Just gives the definition and the fact that each component of a functional graph contains exactly one cycle
- Romero & Zertuche, 2005: Grasping the connectivity of random functional graphs
(doi)
- Lists a number of references from combinatorics and dynamical systems
- Daugulis, 2014: Graph structure of commuting functions (arxiv)
- Studies commuting functions from the viewpoint that two self-maps commute if and only if one is a graph endomorphism of the other’s function graph