Volkmann, L. and Yeo., A. (2004) Hamiltonian paths, containing a given path or collection of arcs, in close to regular multipartite tournaments. Discrete Mathematics, 281 (1-3).
Full text access: Open
Abstract A tournament is an orientation of a complete graph, and in general a multipartite or c-partite tournament is an orientation of a complete c-partite graph. If x is a vertex of a digraph D, then we denote by d+(x) and d−(x) the outdegree and indegree of x, respectively. The global irregularity of a digraph D is defined by ig(D)=max{d+(x),d−(x)}−min{d+(y),d−(y)} over all vertices x and y of D (including x=y). If ig(D)=0, then D is called regular. Let V1,V2,…,Vc be the partite sets of a c-partite tournament D such that |V1||V2||Vc|. If P is a directed path of length q in the c-partite tournament D such that |V(D)|2ig(D)+3q+2|Vc|+|Vc−1|−2, then we prove in this paper that there exists a Hamiltonian path in D, starting with the path P. Examples will show that this condition is best possible. As an application of this theorem, we prove that each arc of a regular multipartite tournament is contained in a Hamiltonian path. Some related results are also presented. Multipartite tournaments; Hamiltonian path; Regular multipartite tournaments
This is a Published version This version's date is: 28/04/2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/82d76c5d-d61b-4899-4db6-2329e4aa9aa1/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 23-Dec-2009
Multipartite tournaments; Hamiltonian path; Regular multipartite tournaments