On Greene-Kleitman's theorem for general digraphs

Linial conjectured that Greene—Kleitman's theorem can be extended to general digraphs. We prove a stronger conjecture of Berge for digraphs having k-optimal path partitions consisting of ‘long’ paths. The same method yields known results for acyclic digraphs, and extensions of various theorems of Greene and Frank to acyclic digraphs.     

Wielandt type theorem for Cartesian product of digraphs

We show that mn-1 is an upper bound of the exponent of the Cartesian product D×E of two digraphs D and E on m,n vertices, respectively and we prove our upper bound is extremal when (m,n)=1. We also find all D and E when the exponent of D×E is mn-1. In addition, when m=n, we prove that the extremal upper bound of exp(D×E) is n²-n+1 and only the Cartesian product, Z_n×W_n, of the directed cycle and Wielandt digraph has exponent equals to this bound.     

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.     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

On randomlyn-cyclic digraphs

A digraphD is called randomlyn-cyclic if for each vertexv ofD, every (directed) path with initial vertexv and having length at mostn – 1 can be extended to av – v (directed) cycle of lengthn. This notion was first introduced by Chartrand, Oellermann and Ruiz [3] and they determined all randomly 3, 4 and 5-cyclic diagraphs. In this paper, we will provide the characterization of randomlyn-cyclic digraphs forn 6.     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

Meyniel's theorem for strongly (p,q) - Hamiltonian digraphs

We give the following theorem: Let D = (V, E) be a strongly (p + q + 1)-connected digraph with n ≥ p + q + 1 vertices, where p and q are nonnegative integers, p ≤ n - 2, n ≥ 2. Suppose that, for each four vertices u, v, w, z (not necessarily distinct) such that {u, v} ∩ {w, z} = Ø, (w, u) ? E, (v, z) ? E, we have id(u) + od(v) + od(w + id(z) ≥ 2 (n + p + q)) + 1. Then D is strongly (p, q)-Hamiltonian.     

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     

On detour homogeneous digraphs

If every vertex of a graph is an endvertex of a hamiltonian path, then the graph is called homogeneously traceable. If we require each vertex of a graph to be an endvertex of a longest path (not necessarily a hamiltonian path), then we call the graph a detour homogeneous graph. The concept of a homogeneously traceable graph was extended to digraphs by Bermond, Simões-Pereira, and C.M. Zamfirescu. Skupień introduced different classes of such digraphs. In this paper we discuss the extension of the concept of a detour homogeneous graph to digraphs.     

On large vertex-symmetric digraphs

There is special interest in the design of large vertex-symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems, a large number of nodes are connected with relatively few links and short paths between the nodes, and each node may execute the same communication software without modifications.In this paper, a method for obtaining new general families of large vertex-symmetric digraphs is put forward. To be more precise, from a k-reachable vertex-symmetric digraph and another (k+1)-reachable digraph related to the previous one, and using a new special composition of digraphs, new families of vertex-symmetric digraphs with small diameter are presented. With these families we obtain new vertex-symmetric digraphs that improve various values of the table of the largest known vertex-symmetric (Δ,D)-digraphs. The paper also contains the (Δ,D)-table for vertex-symmetric digraphs, for Δ≤13 and D≤12.     

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

On critically connected digraphs

A digraph is called critically connected if it is connected, but the deletion of any vertex destroys the connectivity. We prove that every critically connected finite digraph has at least two vertices of outdegree one. As an application, we show that for n ≧ 2, there is no n-connected, non-complete, finite digraph such that the deletion of any n vertices results in a disconnected digraph.     

On DP-coloring of digraphs

DP-coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph $G$ with a list-assignment $L$ to finding an independent transversal in an auxiliary graph with vertex set $\text{◂{}▸}\{\left(v,c\right)|\text{◂+▸}v\in V\left(G\right),\text{◂+▸}c\in L\left(v\right)\}$. In this paper, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs.     

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

On digraphs without antidirected cycles

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let t_r (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t₅(n) ≤ t₆(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t₄(n) = 3(n ? 1) for n ≥ 3.     

On a property ofn-edge-connected digraphs

It is proved that for every pair of verticesx, y in a finiten-edge-connected digraphD there is such a pathP fromx toy that the digraphD′ arising fromD by deleting the edges ofP is (n−1)-edge-connected.     

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.