点击次数：

论文类型：期刊论文

发表时间：2011-07-01

发表刊物：UTILITAS MATHEMATICA

收录刊物：Scopus、SCIE

卷号：85

页面范围：327-331

ISSN号：0315-3681

关键字：Directed graph; Cycle-connectivity; Maximal cycle; Universal arc; Bitournament

摘要：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.