Hits:

Indexed by:期刊论文

Date of Publication:2011-07-01

Journal:UTILITAS MATHEMATICA

Included Journals:Scopus、SCIE

Volume:85

Page Number:327-331

ISSN No.: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.