Speaker: Ngo Dac Tan
Time: 9h30, Thursday, December 6, 2018
Location: Room seminar 6 floor, Building A6, Institute of Mathematics
Abstract: We prove that a digraph $D=(V,A)$ of minimum outdegree 3 without vertex disjoint directed cycles of different lengths is a union of three digraphs $D_1=(V_1,A_1), D_2=(V_2,A_2)$ and $D_3=(V_3,A_3)$ such that $V=V_1cup V_2$, where $V_1cap V_2=emptyset$, $V_2
eemptyset$ but $V_1$ may be empty, $D_1$ is the subdigraph of $D$ induced by $V_1$ and is an acyclic digraph, $D_2$ is the subdigraph of $D$ induced by $V_2$ and is a strong digraph of minimum outdegree 3 without vertex disjoint directed cycles of different lengths, $D_3$ is a subdigraph of $D$ every arc of which has its tail in $V_1$ and its head in $V_2$ and for every vertex $vin V_1$, $d^+_{D_1cup D_3}(v)ge 3$. Moreover, such a decomposition of $D$ is unique. Further, we show that the converse of the above decomposition is also true. For the case of girth 2, we get a classification for such digraphs. |
