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 signed digraphs with all cycles negative

In “On signed digraphs with all cycles negative”, Discrete Appl. Math. 12 (1985) 155–164, F. Harary, J.R. Lundgren and J.S. Maybee, identify certain families of such digraphs: the class of strong and upper digraphs and the class Ū. We give here a characterization of the latter class and new proofs of two results concerning these classes, by using the c-minimal strongly connected digraphs. This note answers some questions of the authors.     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

Destroying cycles in digraphs

For a simple directed graph G with no directed triangles, let β(G) be the size of the smallest subset X ∈ E(G) such that G\X has no directed cycles, and let γ(G) denote the number of unordered pairs of nonadjacent vertices in G. Chudnovsky, Seymour, and Sullivan showed that β(G) ≤ γ(G), and conjectured that β(G) ≤ $\tfrac{{\gamma (G)}} {2}$\tfrac{{\gamma (G)}} {2} . In this paper we prove that β(G)<0.88γ(G).     

Disjoint cycles in digraphs

We show that, for each natural numberk, these exists a (smallest) natural numberf(k) such that any digraph of minimum outdegree at leastf(k) containsk disjoint cycles. We conjecture thatf(k)=2k−1 and verify this fork=2 and we show that, for eachk≧3, the determination off(k) is a finite problem. Dedicated to Paul Erdős on his seventieth birthday     

Oriented hamilton cycles in digraphs

We show that a directed graph of order n will contain n-cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + n^-1/6)n and n is sufficiently large. © 1995 John Wiley & Sons, Inc.     

Hamiltonian cycles in -circulant digraphs

Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.     

Degrees and cycles in digraphs

In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least $\text{?}\text{(n?1)}\text{h}\text{? + 1}$, where n is the number of vertices of the graph and h an integer, 1?h?n?1. The same conditions imply the existence of a path of length $\text{?}\text{(n?1)}\text{h}\text{? + ?}\text{(n?2)}\text{h}\text{?}$. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.     

On hypergraphs without significant cycles

A property of the intersection multigraph of a hypergraph is displayed. This property is then used to obtain an equality connecting the order of the hypergraph, the sizes of its edges and the number of edges of its intersection multigraph. At the end a generalization by Las Vergnas of a result of Lovász is given another proof.     

On hypergraphs without loose cycles

Recently, Mubayi and Wang showed that for $r\ge 4$ and $?\ge 3$, the number of $n$-vertex $r$-graphs that do not contain any loose cycle of length $?$ is at most $2^{O\left(n^{r?1}{(logn)}^{(r?3)∕(r?2)}\right)}$. We improve this bound to $2^{O(n^{r?1}loglogn)}$.     

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

Hamilton cycles in digraphs of unitary matrices

A set S⊆V is called a q⁺-set (q^--set, respectively) if S has at least two vertices and, for every u∈S, there exists v∈S,v≠u such that N⁺(u)∩N⁺(v)≠∅ (N^-(u)∩N^-(v)≠∅, respectively). A digraph D is called s-quadrangular if, for every q⁺-set S, we have |∪{N⁺(u)∩N⁺(v):u≠v,u,v∈S}|?|S| and, for every q^--set S, we have |∪{N^-(u)∩N^-(v):u,v∈S)}?|S|. We conjecture that every strong s-quadrangular digraph has a Hamilton cycle and provide some support for this conjecture.     

Orientations of hamiltonian cycles in large digraphs

We prove that, with some exceptions, every digraph with n ≥ 9 vertices and at least (n – 1) (n – 2) + 2 arcs contains all orientations of a Hamiltonian cycle.     

Decompositions of digraphs into paths and cycles

It is shown that in a digraph G, there is an elementary directed path or an elementary directed cycle meeting all inclusion-maximal demi-cocycles of G. This theorem is used to obtain an upper bound on the cardinality of a minimal partition of the arc set of G into directed paths and cycles.     

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 the number of paths and cycles for almost all graphs and digraphs

In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK _n (orK* _n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK _n (respectivelyK* _n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality.     

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.