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.
Asked
Active
Viewed 29 times
1
-
Is this digraph connected? If so, I would guess it's called a (directed) cycle graph. – Arthur Apr 24 '18 at 12:56
-
@Arthur It may not. – Garmekain Apr 24 '18 at 13:03
-
It will in general be a graph composed of directed cyclic components, right? – Jul 27 '18 at 02:26
1 Answers
2
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).
Ethan Splaver
- 10,613