On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

Upward straight-line embeddings of directed graphs into point sets

In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position.     

Primitive digraphs with the largest scrambling index

The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). In [M. Akelbek, S. Kirkland, Coefficients of ergodicity and the scrambling index, preprint] we gave the upper bound on k(D) in terms of the order and the girth of a primitive digraph D. In this paper, we characterize all the primitive digraphs such that the scrambling index is equal to the upper bound.     

Computing upward topological book embeddings of upward planar digraphs

We describe a unified approach for studying book, point-set, and simultaneous embeddability problems of upward planar digraphs. The approach is based on a linear time strategy to compute an upward planar drawing of an upward planar digraph such that all vertices are collinear. Besides having impact in relevant application domains of graph drawing and computational geometry, the presented results open new research directions in the area of upward planarity with constraints of the positions of the vertices.     

Graph Mates

A weighted digraph graph D is said to be doubly stochastic if all the weights of the edges in D are in [0, 1] and sum of the weights of the edges incident to each vertex in D is one. Let Ω(G) be denoted as set of all doubly stochastic digraphs with n vertices. We defined a Graph Mates in Ω(G) and derived a necessary and sufficient condition for two doubly stochastic digraphs are to be a Graph Mates.     

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.     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

Digraphs with real and gaussian spectra

The conventional binary operations of cartesian product, conjunction, and composition of two digraphs D₁ and D₂ are observed to give the sum, the product, and a more complicated combination of the spectra of D₁ and D₂ as the resulting spectrum. These formulas for analyzing the spectrum of a digraph are utilized to construct for any positive integer n, a collection of n nonisomorphic strong regular nonsymmetric digraphs with real spectra. Further, an infinite collection of strong nonsymmetric digraphs with nonzero gaussian integer value is found. Finally, for any n, it is shown that there are n cospectral strong nonsymmetric digraphs with integral spectra.     

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.     

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.     

Longest path partitions in generalizations of tournaments

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ₁,λ₂, such that λ₁+λ₂ equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D₁ and D₂, such that the order of a longest path in D_i is at most λ_i, for i=1,2.We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.     

Lower bounds for the energy of digraphs

The energy of a digraph D is defined as , where z₁,…,z_n are the eigenvalues of D. In this article we find lower bounds for the energy of digraphs in terms of the number of closed walks of length 2, extending in this way the result obtained by Caporossi et al. [G. Caporossi, D. Cvetkovi?, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996]: for all graphs G with m edges. Also, we study digraphs with three eigenvalues.     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.     

Irregularity strength of digraphs

It is an elementary exercise to show that any non-trivial simple graph has two vertices with the same degree. This is not the case for digraphs and multigraphs. We consider generating irregular digraphs from arbitrary digraphs by adding multiple arcs. To this end, we define an irregular labeling of a digraph D to be an arc-labeling of the digraph such that the ordered pairs of the sums of the in-labels and out-labels at each vertex are all distinct. We define the strength of D to be the smallest of the maximum labels used across all irregular labelings. Similar definitions for graphs have been studied extensively and a different formulation of digraph irregularity was given in [H. Hackett, Irregularity strength of graphs and digraphs, Masters Thesis, University of Louisville, 1995]. Here we continue the study of irregular labelings of digraphs. We give a general lower bound on and determine exactly for tournaments, directed paths and cycles and the orientation of the path where all vertices have either in-degree 0 or out-degree 0. We also determine the irregularity strength of a union of directed cycles and a union of directed paths, the latter which requires a new result pertaining to finding circuits of given lengths containing prescribed vertices in the complete symmetric digraph with loops.     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

On complexity of Minimum Leaf Out-Branching problem

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree zero. Gutin, Razgon and Kim [G. Gutin, I. Razgon, E.J. Kim, Minimum leaf out-branching problems, in: Proc. 4th International Conference on Algorithmic Aspects in Information and Management, AAIM’08, in: Lect. Notes Comput. Sci., vol. 5034 2008, pp. 235-246] proved that MinLOB is polynomial time solvable for acyclic digraphs which are exactly the digraphs of directed path-width (DAG-width, directed tree-width, respectively) 0. We investigate how much one can extend this polynomiality result. We prove that already for digraphs of directed path-width (directed tree-width, DAG-width, respectively) 1, MinLOB is NP-hard. On the other hand, we show that for digraphs of restricted directed tree-width (directed path-width, DAG-width, respectively) and a fixed integer k, the problem of checking whether there is an out-branching with at most k leaves is polynomial time solvable.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

Maximum Directed Cuts in Graphs with Degree Constraints

The Max Cut problem is an NP-hard problem and has been studied extensively. Alon et?al. (J Graph Theory 55:1–13, 2007) studied a directed version of the Max Cut problem and observed its connection to the Hall ratio of graphs. They proved, among others, that if an acyclic digraph has m edges and each vertex has indegree or outdegree at most 1, then it has a directed cut of size at least 2m/5. Lehel et?al. (J Graph Theory 61:140–156, 2009) extended this result by replacing the “acyclic digraphs” with the “digraphs containing no directed triangles”. In this paper, we characterize the acyclic digraphs with m edges whose maximum dicuts have exactly 2m/5 edges, and our approach gives an alternative proof of the result of Lehel et?al. We also show that there are infinitely many positive rational numbers β < 2/5 for which there exist digraphs D (with directed triangles) such that each vertex of D has indegree or outdegree at most 1, and any maximum directed cut in D has size precisely β|E(D)|.