Some results on the existence of Hamiltonian cycles in the generalized sum of digraphs

详细信息    查看全文

• 作者：Narda Cordero-Michel ^{narda@ciencias.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; Hortensia Galeana-Sá ; nchez ^{hgaleana@matem.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; Ilan A. Goldfeder ; ^{ilan.goldfeder@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; ^{ilan@ciencias.unam.mx" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Generalization of tournaments ; Bipartite tournaments ; Hamiltonian cycles ; Generalized sum of digraphs ; Cycle factors
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 June 2016
• 年：2016
• 卷：339
• 期：6
• 页码：1763-1770
• 全文大小：634 K

文摘

Let 3" class="mathmlsrc">365X16300255&_mathId=si23.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=5f0c8f0d26bb6da625930f4aabbcc23a" title="Click to view the MathML source">D₁,…,D_k be a family of pairwise vertex-disjoint digraphs. The generalized sum   of 3" class="mathmlsrc">365X16300255&_mathId=si23.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=5f0c8f0d26bb6da625930f4aabbcc23a" title="Click to view the MathML source">D₁,…,D_k, denoted by 365X16300255&_mathId=si25.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=f9564df2d1fc67e1753582731118b22e" title="Click to view the MathML source">D₁⊕⋯⊕D_k$D_1\oplus \cdots \oplus D_k$, is the set of all digraphs 365X16300255&_mathId=si26.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=d894bff86d37ef9183be7dbaf9c07d19" title="Click to view the MathML source">D$D$ which satisfies: (i) 365X16300255&_mathId=si27.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=6e348101b0c509403cd4c9c32557b183">3" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16300255-si27.gif">$V\left(D\right)={\cup }_{i=1}^{k}V\left(D_i\right)$, (ii) 365X16300255&_mathId=si28.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=4bb9df2328bf570c7ab70bad110d40e6" title="Click to view the MathML source">D[V(D_i)]≅D_i$D\left[V\left(D_i\right)\right]\cong D_i$ for every 365X16300255&_mathId=si29.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=56c6ddeb620bf2cecb1109662772a973" title="Click to view the MathML source">i∈[k]$i\in \left[k\right]$ and (iii) between each pair of vertices in different summands of 365X16300255&_mathId=si26.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=d894bff86d37ef9183be7dbaf9c07d19" title="Click to view the MathML source">D$D$ there is exactly one arc. When each 31" class="mathmlsrc">365X16300255&_mathId=si31.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=97100ad9b7d54fc9030094f6806f4305" title="Click to view the MathML source">D_i has no arcs, we have that 365X16300255&_mathId=si25.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=f9564df2d1fc67e1753582731118b22e" title="Click to view the MathML source">D₁⊕⋯⊕D_k$D_1\oplus \cdots \oplus D_k$ is a set of 33" class="mathmlsrc">365X16300255&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=1def7244bf9af591d79e2dd28f2391ef" title="Click to view the MathML source">k-partite digraphs. Moreover, for each tournament 34" class="mathmlsrc">365X16300255&_mathId=si34.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=4a39adbc42894fbcd6e53c7b80dbc964" title="Click to view the MathML source">T on 33" class="mathmlsrc">365X16300255&_mathId=si33.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=1def7244bf9af591d79e2dd28f2391ef" title="Click to view the MathML source">k vertices, we always have that 36" class="mathmlsrc">365X16300255&_mathId=si36.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=27d1ef46d54e6f26029d2ded61003b8b" title="Click to view the MathML source">T[D₁,…,D_k], the composition of digraphs, is in 37" class="mathmlsrc">365X16300255&_mathId=si37.gif&_user=111111111&_pii=S0012365X16300255&_rdoc=1&_issn=0012365X&md5=c62598bc15bdc4c69093c28b8732506e" title="Click to view the MathML source">D₁⊕⋯⊕D_n. In this work, we give some results on the existence or the non-existence of Hamiltonian cycles and cycle-factors in such digraphs. Particularly, we prove a generalization of the characterization of Hamiltonian semicomplete bipartite digraphs due to Gutin, Häggkvist and Manoussakis.