- Tytuł:
- Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
- Autorzy:
-
Li, Ruijuan
Han, Tingting - Powiązania:
- https://bibliotekanauki.pl/articles/31342322.pdf
- Data publikacji:
- 2018-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
locally semicomplete digraph
local tournament
round decomposable
arc-disjoint
Hamiltonian cycle
Hamiltonian path - Opis:
- Let D = (V,A) be a digraph; if there is at least one arc between every pair of distinct vertices of D, then D is a semicomplete digraph. A digraph D is locally semicomplete if for every vertex x, the out-neighbours of x induce a semicomplete digraph and the in-neighbours of x induce a semicomplete digraph. A locally semicomplete digraph without 2-cycle is a local tournament. In 2012, Bang-Jensen and Huang [J. Combin Theory Ser. B 102 (2012) 701–714] concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs, and proposed the conjecture that every 3-strong local tournament has two arc-disjoint Hamiltonian cycles. According to Bang-Jensen, Guo, Gutin and Volkmann, locally semicomplete digraphs have three subclasses: the round decomposable; the non-round decomposable which are not semicomplete; the non-round decomposable which are semicomplete. In this paper, we prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint Hamiltonian cycles, which implies that the conjecture holds for the round decomposable local tournaments. Also, we characterize the 2-strong round decomposable local tournaments each of which contains a Hamiltonian path P and a Hamiltonian cycle arc-disjoint from P.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 477-490
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł