Longest paths in digraphs

In this paper, we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of given length, and we characterize the extremal graphs.     

Longest paths and cycles in bipartite oriented graphs

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2), on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.     

On super-edge-connected digraphs and bipartite digraphs

A maximally edge-connected digraph is called super-λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super-λ are presented in terms of parameters such as diameter and minimum degree. Similar results are also given for bipartite digraphs. As a corollary, some characterizations of super-λ graphs and bipartite graphs are obtained. © 1929 John Wiley & Sons, Inc.     

Supereulerian bipartite digraphs

A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity of a digraph D is not less than the independence number , then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying , then D is supereulerian. Consequently, every bipartite digraph D satisfying is supereulerian. The bound of our main result is best possible.     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

Path number of bipartite digraphs

In this paper it is proved that the path number of the complete symmetric bipartite digraph on n and n vertices is n + 1, thereby establishing a conjecture of Chein.     

Disjoint paths in symmetric digraphs

Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration.     

Covering digraphs by paths

The problems of minimum edge and minimum vertex covers by paths are discussed. The results relate to papers by Gallai-Milgram, Meyniel, Alspach-Pullman and others. One of the main results is concerned with partially ordered sets.     

Orientations of Hamiltonian cycles in bipartite digraphs

The main result of the paper is the following Theorem. Let D=(X,Y,A) be a bipartite, balanced digraph of order 2n and size at least 2n²–2n+3. Then D contains an almost symmetric Hamiltonian cycle (i.e. a Hamiltonian cycle in which at least 2n–1 arcs are symmetric edges), unless D has a vertex which is not incident to any symmetric edge of D.This theorem implies a number of results on cycles in bipartite, balanced digraphs, including some recent results of N. Chakroun, M. Manoussakis and Y. Manoussakis.     

On cycles and paths in digraphs

The purpose of this communication is to announce some sufficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].     

On monochromatic paths in edge-coloured digraphs

Let G be a directed graph whose edges are coloured with two colours. Call a set S of vertices of Gindependent if no two vertices of S are connected by a monochromatic directed path. We prove that if G contains no monochromatic infinite outward path, then there is an independent set S of vertices of G such that, for every vertex x not in S, there is a monochromatic directed path from x to a vertex of S. In the event that G is infinite, the proof uses Zorn's lemma. The last part of the paper is concerned with the case when G is a tournament.     

Infinite Hamiltonian paths in Cayley digraphs

Let Cay(S:H) be the Cayley digraph of the generators S in the group H. A one-way infinite Hamiltonian path in the digraph G is a listing of all the vertices [ν_i:1⩽i<∞], such that there is an arc from ν_i to ν₁₊₁. A two-way infinite Hamiltonian path is similarly defined, with i ranging from −∞ to ∞. In this paper, we give conditions on S and H for the existence of one- and two-way infinite Hamiltonian paths in Cay(X:H). Two of our results can be summarized as follows. First, if S is countably infinite and H is abelian, then Cay(S:H) has one- and two-way Hamiltonian paths if and only if it is strongly connected (except for one infinite family). We also give necessary and sufficient conditions on S for Cay(S:H) to be strongly connected for a large class of Cayley digraphs. Second, we show that any Cayley digraph of a countable locally finite group has both one- and two-way infinite Hamiltonian paths. As a lemma, we give a relation between the strong connectivity and the outer valence of finite vertex-transitive digraphs.     

Antidirected paths in 5-chromatic digraphs

Let $T_5$ be the regular 5-tournament. B. Grünbaum proved that $T_5$ is the only 5-tournament which contains no copy of the antidirected path $P_4$. In this Note, we prove that, except for $T_5$, any connected 5-chromatic oriented digraph in which each vertex has out-degree at least two contains a copy of $P_4$. It will be shown, by an example, that the condition that each vertex has out-degree at least two is indispensable. To cite this article: A. El Sahili, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Neighborhood and degree conditions for super-edge-connected bipartite digraphs

A graph or digraph D is called super-λ, if every minimum edge cut consists of edges incident to or from a vertex of minimum degree, where λ is the edge-connectivity of D. Clearly, if D is super-λ, then λ = δ, where δ is the minimum degree of D. In this paper neighborhood, degree sequence, and degree conditions for bipartite graphs and digraphs to be super-λ are presented. In particular, the neighborhood condition generalizes the following result by Fiol [7]: If D is a bipartite digraph of order n and minimum degree δ ≥ max{3, ?(n + 3)/4?}, then D is super-λ.     

Acyclically pushable bipartite permutation digraphs: An algorithm

Given a digraph D=(V,A) and an X⊆V, D^X denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an X⊆V such that D^X is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an O(m²) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that D^X is acyclic. (Huang, MacGillivray and Yeo's result clearly implies an O(n⁸) time algorithm to decide but the polynomiality of constructing X was still open.)We define a strongly acyclic digraph as a digraph D such that D^X is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33]. In particular, we avoid decomposing the graph into triconnected components.We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that D^X is acyclic or a proof that D is not acyclically pushable.