On a cyclic connectivity property of directed graphs |
| |
Authors: | Alice Hubenko |
| |
Affiliation: | Department of Mathematics, University of California, Riverside, CA 92521, USA |
| |
Abstract: | Let us call a digraph D cycle-connected if for every pair of vertices u,v∈V(D) there exists a cycle containing both u and v. In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge e∈E(D) such that for every w∈V(D) there exists a cycle C such that w∈V(C) and e∈E(C)?In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments. |
| |
Keywords: | Directed graph Bitournament Directed cycle Cycle-connectivity Universal edge |
本文献已被 ScienceDirect 等数据库收录! |
|