Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2011-07-01

Journal: UTILITAS MATHEMATICA

Included Journals: SCIE、Scopus

Volume: 85

Page Number: 327-331

ISSN: 0315-3681

Key Words: Directed graph; Cycle-connectivity; Maximal cycle; Universal arc; Bitournament

Abstract: A digraph D is cycle-connected if for every pair of vertices u, v is an element of V(D) there exists a directed cycle in D containing both u and v. A. Hubenko [On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bitournament has a universal arc, and further raised the following problem. Assume that D is a cycle-connected bitournament and C is a maximal cycle of D. Are all arcs of C universal? In the present paper, we show that there exists a cycle-connected bipartite tournament such that at least one arc of one of its maximal cycles is not universal. More over, we show that there exists a simple bipartite cycle-connected digraph such that at least one arc of one of its maximal cycles is not universal, and that there exists a simple bipartite cycle-connected digraph such that all arcs of its maximal cycles are universal.