Outpaths of all length of an arc in regular multipartite tournaments
Guo Qiao-pin · 2014
An(l- l)-outpath of an arc x_1x_2 in a multipartite tournament is a path x_1x_2…x_1 of length l- 1 starting with x_1x_2,such that either x_1 and x_1 are in the same partite set or x_1 dominates x_1.Specially,x_1x_2… x_1x_2 is a Hamilton cycle when l = |V(D)| and x_1 dominates x_1.Guo(Discrete Appl Math 95(1999) 273-277) proved that every arc of a regular c-partite tournament with c 3has a(k- l)-outpath for each k 6 {3,4,…,c}.As a generalization,this paper proves that every arc in a regular c-partite tournament with c ≥ 5 has a(k- l)-outpath for each k ∈ {3,4,…,|V(D)|}.Furthermore,using the method of path-contracting,the paper also proves the following result:Let D be a regular c-partite tournament.If c ≥ 8 and there are two vertices in every partite set,then each arc in D is contained in a Hamilton cycle.This result gives a partial support to the conjecture posed by Volkmann and Yeo(Discrete Math 281(2004) 267-276) that each arc of a regular multipartite tournament is contained in a Hamilton cycle.