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.     

Connection digraphs and second-order line digraphs

The primary result of this paper gives a set of necessary and sufficient conditions for a digraph to be second-order line digraph of some digraph. A directed analogue of the concept of an intersection graph, defined for collections of ordered pairs of sets and called the connection digraph, is used to achieve this result.     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Split digraphs

We generalize the class of split graphs to the directed case and show that these split digraphs can be identified from their degree sequences. The first degree sequence characterization is an extension of the concept of splittance to directed graphs, while the second characterization says a digraph is split if and only if its degree sequence satisfies one of the Fulkerson inequalities (which determine when an integer-pair sequence is digraphic) with equality.     

Powerful digraphs

We introduce the concept of a powerful digraph and establish that a powerful digraph structure is included into the saturated structure of each nonprincipal powerful type p possessing the global pairwise intersection property and the similarity property for the theories of graph structures of type p and some of its first-order definable restrictions (all powerful types in the available theories with finitely many (> 1) pairwise nonisomorphic countable models have this property). We describe the structures of the transitive closures of the saturated powerful digraphs that occur in the models of theories with nonprincipal powerful 1-types provided that the number of nonprincipal 1-types is finite. We prove that a powerful digraph structure, considered in a model of a simple theory, induces an infinite weight, which implies that the powerful digraphs do not occur in the structures of the available classes of the simple theories (like the supersimple or finitely based theories) that do not contain theories with finitely many (> 1) countable models.     

Double-super-connected digraphs

A strongly connected digraph D is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph D is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree.     

Hypotraceable digraphs

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D - v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo-Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.     

Game-perfect digraphs

In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The players move alternately, where a move of Bob consists in coloring a vertex, and a move of Alice in coloring a vertex or missing the turn. The game ends when Bob is unable to move. Alice wins if every vertex is colored at the end, otherwise Bob wins. This game is a variant of a graph coloring game proposed by Bodlaender (Int J Found Comput Sci 2:133?C147, 1991). The A-game chromatic number of D is the smallest cardinality of a color set C, so that Alice has a winning strategy for the game played on D with C. A digraph is A-perfect if, for any induced subdigraph H of D, the A-game chromatic number of H equals the size of the largest symmetric clique of H. We characterize some basic classes of A-perfect digraphs, in particular all A-perfect semiorientations of paths and cycles. This gives us, as corollaries, similar results for other games, in particular concerning the digraph version of the usual game chromatic number.     

Descendant-homogeneous digraphs

The descendant setdesc(α) of a vertex α in a digraph D is the set of vertices which can be reached by a directed path from α. A subdigraph of D is finitely generated if it is the union of finitely many descendant sets, and D is descendant-homogeneous if it is vertex transitive and any isomorphism between finitely generated subdigraphs extends to an automorphism. We consider connected descendant-homogeneous digraphs with finite out-valency, specially those which are also highly arc-transitive. We show that these digraphs must be imprimitive. In particular, we study those which can be mapped homomorphically onto Z and show that their descendant sets have only one end.There are examples of descendant-homogeneous digraphs whose descendant sets are rooted trees. We show that these are highly arc-transitive and do not admit a homomorphism onto Z. The first example (Evans (1997) [6]) known to the authors of a descendant-homogeneous digraph (which led us to formulate the definition) is of this type. We construct infinitely many other descendant-homogeneous digraphs, and also uncountably many digraphs whose descendant sets are rooted trees but which are descendant-homogeneous only in a weaker sense, and give a number of other examples.     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

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.     

Maximum path digraphs

In this paper we solve the following problem: Given an integer m, construct a digraph with exactly one source s, exactly one sink t and exactly m arcs such that the number of paths from s to t is maximized.     

List coloring digraphs

The dichromatic number of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann‐Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this article, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as . We finally give a Brooks‐type upper bound on the list dichromatic number of digon‐free digraphs.     

Connectivity in digraphs

Let c(x,y) denote the maximum number of edge-disjoint directed paths joining x to y in the digraph G. It is shown that, for a given point a of G, c(a,x) ≤ c(x,a) for any x implies that the outdegree of a is ≤ its indegree. An immediate consequence is Kotzig's conjecture: Given a digraph G, c(x,y) = c(y,x) for every x, y if and only if the graph is pseudo-symmetric, i.e., each point has the same indegree and outdegree (the “if” part having been proved by Kotzig). The same method is applied to prove a weakened form of a conjecture of N. Robertson, while the original conjecture is disproved.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.