A digraph (direct graph) consists of a set $V$ of vertices and a set $E$ of directed edges $v\to v'$. A multidigraph is a digraph in which $E$ is a multiset, so edges may appear multiple times in $E$, or equivalently, $E$ is a set of directed edges that are assigned multiplicities.

Is there a standard name for a multidigraph with the following property? For each vertex $v\in V$, there is at most one $v'\in V$ such that the edge $v\to v'$ is in $E$, although that edge is of course allowed to appear multiple times in $E$.

I looked through the list of various types of graphs on Wikipedia, but didn't see this one. (For a digraph that's not "multi", one could say "digraph with all out-degrees 0 or 1," but even that seems clumsy.)

  • $\begingroup$ @JulesLamers Thanks. So if I understand what you're saying, a linear digraph is a digraph in which each vertex has at most one out-arrow. (Also, just for curiosity, why do you say "a collection of"? Does the word "graph" imply connected?) $\endgroup$ – Joe Silverman Jun 13 '18 at 15:36
  • $\begingroup$ if each vertex has a unique successor, then we have (ignoring parallel arcs) a tree, that is directed from the leaf nodes towards the root; maybe that helps in identifying a name for the multi-digraph. If it is not connected, then that applies to the connected components. $\endgroup$ – Manfred Weis Jun 13 '18 at 15:41
  • $\begingroup$ @ManfredWeis Thank you, but having a unique successor isn't enough to force the connected components to be trees. One could alternatively have a cycle, with chains of vertices hanging off of one or more of the vertices in the cycle. For example, I want to allow digraphs such as A --> B --> C --> B. But I do also want to allow components that are trees. $\endgroup$ – Joe Silverman Jun 13 '18 at 15:49
  • $\begingroup$ A different line of thought: there is a functional dependence between a vertex and its successor if it exists; so maybe "function graph" covers both cases (in case of functions one also has the situation that they are not always defined for all arguments, which would correspond to the case of leaf nodes). I have however no idea, how to interpret the multi-arcs in that analogy. $\endgroup$ – Manfred Weis Jun 13 '18 at 16:28
  • $\begingroup$ If we define leaf nodes as being their own successor, then we have an endomorphism on the vertices. $\endgroup$ – Manfred Weis Jun 13 '18 at 16:38

I haven't seen the multigraph version, but non-multi directed graphs with at most one outgoing neighbor per vertex have been called directed pseudoforests, and with exactly one outgoing neighbor they are also called functional graphs or maximal directed pseudoforests.

| cite | improve this answer | |
  • $\begingroup$ *Directed pseudoforest" is an interesting name, I hadn't seen that before. I assume that if the graph is connected, then it's a "directed pseudotree,", and it becomes a forest if there is more than one tree. For the multigraph version, I guess one could just add the "multi" somewhere, say *multidirected pseudoforest". $\endgroup$ – Joe Silverman Jun 13 '18 at 20:54

If you didn't have multiple edges, you could call it a deterministic digraph, because it would correspond to a function $\mathsf{succ}:V\to V$. This is the dynamical interpretation. With multiple edges, you could call it deterministic with multiple routes: at every step, the following position is uniquely determined by the current position, but there are multiple routes to get there.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks. But it's not quite a function from $V$ to $V$, because not every vertex needs to have an out-arrow, so there may be sinks. You're correct that what I have in mind is a dynamical interpretation, but I may want to include some points where the "function" is not defined, so it's not quite a function in the usual sense. Maybe a dynamical digraph would be a reasonable name, but I wasn't so much looking for suggestions for good names as I was trying to find out if it already has a standard name, since it's always better to use terminology consistent with past usage. $\endgroup$ – Joe Silverman Jun 13 '18 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.