Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
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 d...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2023 |
| _version_ | 1797757759491407872 |
|---|---|
| author | Li Ruijuan Han Tingting |
| author_facet | Li Ruijuan Han Tingting |
| author_sort | Li Ruijuan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T18:19:11Z |
| format | Article |
| id | doaj.art-619eb986aab84c30bd6e2269616c4656 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:11Z |
| publishDate | 2018-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-619eb986aab84c30bd6e2269616c46562023-08-02T08:59:12ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-05-0138247749010.7151/dmgt.2023dmgt.2023Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete DigraphsLi Ruijuan0Han Tingting1School of Mathematical Sciences, Shanxi University, 030006Taiyuan, P.R. ChinaSchool of Mathematical Sciences, Shanxi University, 030006Taiyuan, P.R. ChinaLet 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.https://doi.org/10.7151/dmgt.2023locally semicomplete digraphlocal tournamentround decomposablearc-disjointhamiltonian cyclehamiltonian path05c20 |
| spellingShingle | Li Ruijuan Han Tingting Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs Discussiones Mathematicae Graph Theory locally semicomplete digraph local tournament round decomposable arc-disjoint hamiltonian cycle hamiltonian path 05c20 |
| title | Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs |
| title_full | Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs |
| title_fullStr | Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs |
| title_full_unstemmed | Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs |
| title_short | Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs |
| title_sort | arc disjoint hamiltonian cycles in round decomposable locally semicomplete digraphs |
| topic | locally semicomplete digraph local tournament round decomposable arc-disjoint hamiltonian cycle hamiltonian path 05c20 |
| url | https://doi.org/10.7151/dmgt.2023 |
| work_keys_str_mv | AT liruijuan arcdisjointhamiltoniancyclesinrounddecomposablelocallysemicompletedigraphs AT hantingting arcdisjointhamiltoniancyclesinrounddecomposablelocallysemicompletedigraphs |