HOẠT ĐỘNG TRONG TUẦN

A decomposition for digraphs of minimum outdegree 3 without vertex disjoint directed cycles of different lengths (phần 2).
Báo cáo viên: Ngô Đắc Tân

Thời gian: 9h30, thứ 5, ngày 13/12/2018
Địa điểm: Phòng 611- 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt.
Tóm tắt: 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

Trở lại