Every cycle-connected multipartite tournament has a universal arc

A digraph DD is cycle-connected if for every pair of vertices u,v∈V(D)u,v∈V(D) there exists a directed cycle in DD containing both uu and vv. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1–12] posed the following problem. Let DD be a cycle-connected digraph. Does there exist a universal arc in DD, i.e., an arc e∈A(D)e∈A(D) such that for every vertex w∈V(D)w∈V(D) there is a directed cycle in DD containing both ee and ww?A cc-partite or multipartite tournament is an orientation of a complete cc-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018–1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.