Search

Abstract: An arc going out from a vertex x in a digraph is called an out-arc of x. Yao et al. [Discrete Appl. Math. 99 (2000) 245–249] proved that every strong tournament contains a vertex x such that all out-arcs of x are pancyclic. Recently, Yeo [J. Graph Theory 50 (2005) 212–219] proved that each 3-strong tournament contains two such vertices. In this paper, we confirm that Yeo''s result is also true for 2-strong tournaments. Our proof implies a polynomial algorithm to find two such vertices. [Copyright &y& Elsevier]

Abstract: In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle bases. In this paper, we offer an unitary classification accommodating these three classes and further including the following four relevant classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The classification is complete in that, for each ordered pair of classes considered, we either prove that holds for every graph or provide a counterexample graph for which . The seven notions of cycle bases are distinct (either or is exhibited for each pair ). All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the MCB problem naturally associated to each one of these seven classes. Furthermore, we provide a linear time algorithm for computing a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases are of direct use. [Copyright &y& Elsevier]