Name of a digraph such that all its vertices are carriers?

30 Views Asked by At

I'm looking for the name of a digraph such that all its vertices have in- and out-degree of $1$, or, what is the same, the name of a digraph such that all its vertices are carriers.

1

There are 1 best solutions below

0
On

Given any digraph $D=(V,E)$ we have that:

$$\forall v\in V\left(\text{deg}_{+}(v)=\text{deg}_{-}(v)=1\right)\iff \exists \sigma \in \text{Sym}(V):E=\{(v,\sigma(v))\subseteq V^2:v\in V\}$$

Where $\text{Sym}(V)$ is the symmetric group on the set $V$. This is equivalent to saying $D$ will have no isolated vertices and every weakly connected component of $D$ will either be a directed cycle or a directed double-ray (intuitively this can be thought of as arcs attached head to tail infinitely in both directions, for example the hasse diagram of the integers partially ordered by size is a double-ray).