Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths

Tytuł:
A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths
Autorzy:
Tan, Ngo Dac
Data publikacji:
2023
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph with minimum outdegree 3
vertex disjoint cycles
cycles of different lengths
acyclic digraph
strong digraph
Źródło:
Discussiones Mathematicae Graph Theory; 2023, 43, 2; 573-581
2083-5892
Język:
angielski
Prawa:
CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
We say that a digraph $D=(V,A)$ admits a good decomposition $D=D_1\cup D_2\cup D_3$ if $D_1=(V_1,A_1), D_2=(V_2,A_2)$ and $D_3=(V_3,A_3)$ are such subdigraphs of $D$ that $V=V_1\cup V_2$ with $V_1\cap V_2=\emptyset$, $V_2\ne\emptyset$ 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 and $D_3$ is a subdigraph of $D$, every arc of which has its tail in $V_1$ and its head in $V_2$. In this paper, we show that a digraph $D=(V,A)$ with minimum outdegree 3 has no vertex disjoint directed cycles of different lengths if and only if $D$ admits a good decomposition $D=D_1\cup D_2\cup D_3$, where $D_1=(V_1,A_1), D_2=(V_2,A_2)$ and $D_3=(V_3,A_3)$ are such that $D_2$ has minimum outdegree 3 and no vertex disjoint directed cycles of different lengths and for every vertex $v\in V_1$, $d_{D_1\cup D_3}^+ (v)\ge 3$. Moreover, when such a good decomposition for $D$ exists, it is unique. By these results, the investigation of digraphs with minimum outdegree 3 having no vertex disjoint directed cycles of different lengths can be reduced to the investigation of strong such digraphs. Further, we classify strong digraphs with minimum outdegree 3 and girth 2 having no vertex disjoint directed cycles of different lengths.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies