Article ID Journal Published Year Pages File Type
4647065 Discrete Mathematics 2016 8 Pages PDF
Abstract

Let D1,…,DkD1,…,Dk be a family of pairwise vertex-disjoint digraphs. The generalized sum   of D1,…,DkD1,…,Dk, denoted by D1⊕⋯⊕DkD1⊕⋯⊕Dk, is the set of all digraphs DD which satisfies: (i) V(D)=∪i=1kV(Di), (ii) D[V(Di)]≅DiD[V(Di)]≅Di for every i∈[k]i∈[k] and (iii) between each pair of vertices in different summands of DD there is exactly one arc. When each DiDi has no arcs, we have that D1⊕⋯⊕DkD1⊕⋯⊕Dk is a set of kk-partite digraphs. Moreover, for each tournament TT on kk vertices, we always have that T[D1,…,Dk]T[D1,…,Dk], the composition of digraphs, is in D1⊕⋯⊕DnD1⊕⋯⊕Dn. 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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,