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(Φ).     

The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G=(V,A), the subdigraph of G induced by a subset X of V is denoted by G[X]. With each digraph G=(V,A) is associated its dual G^?=(V,A^?) defined as follows: for any x,y∈V, (x,y)∈A^? if (y,x)∈A. Two digraphs G and H are hemimorphic if G is isomorphic to H or to H^?. Given k>0, the digraphs G=(V,A) and H=(V,B) are k-hemimorphic if for every X⊆V, with |X|≤k, G[X] and H[X] are hemimorphic. A class C of digraphs is k-recognizable if every digraph k-hemimorphic to a digraph of C belongs to C. In another vein, given a digraph G=(V,A), a subset X of V is an interval of G provided that for a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For example, 0?, {x}, where x∈V, and V are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable.     

A family of weakly distance-regular digraphs of girth 2

A family of commutative weakly distance-regular digraphs of girth 2 was classified in [K. Wang, Commutative weakly distance-regular digraphs of girth 2, European J. Combin. 25 (2004) 363-375]. In this paper, we classify this family of digraphs without the assumption of commutativity.     

Chronological orderings of interval digraphs

An interval digraph is the intersection digraph of a family of ordered pairs of intervals on the real line; the family is an interval representation of the digraph. It is well known that an interval digraph has many representations that differ in the order of the endpoints of the intervals on the line. This paper generalizes the corresponding results on interval graphs by Skrien [Chronological orderings of interval graphs, Discrete Appl. Math. 8 (1984) 69-83] and describes how, given an interval digraph, the order of intervals of one representation differs from another.     

The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

For two or more classes of points in R^d with d≥1, the class cover catch digraphs (CCCDs) can be constructed using the relative positions of the points from one class with respect to the points from one or all of the other classes. The CCCDs were introduced by Priebe et al. [C.E. Priebe, J.G. DeVinney, D.J. Marchette, On the distribution of the domination number of random class catch cover digraphs. Statistics and Probability Letters 55 (2001) 239-246] who investigated the case of two classes, X and Y. They calculated the exact (i.e., finite sample) distribution of the domination number of the CCCDs based on X points relative to Y points both of which were uniformly distributed on a bounded interval. We investigate the distribution of the domination number of the CCCDs based on data from non-uniform X points on an interval with end points from Y. Then we extend these calculations for multiple Y points on bounded intervals.     

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.     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

Weakly distance-regular digraphs

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented.     

Gaussian integral circulant digraphs

The spectrum of a digraph in general contains real and complex eigenvalues. A digraph is called a Gaussian integral digraph if it has a Gaussian integral spectrum that is all eigenvalues are Gaussian integers. In this paper, we consider Gaussian integral digraphs among circulant digraphs.     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

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.     

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.     

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.     

Kernels of digraphs with finitely many ends

According to Richardson’s theorem, every digraph $G$ without directed odd cycles that is either (a) locally finite or (b) rayless has a kernel (an independent subset $K$ with an incoming edge from every vertex in $G?K$). We generalize this theorem showing that a digraph without directed odd cycles has a kernel when (a) for each vertex, there is a finite set separating it from all rays, or (b) each ray contains at most finitely many vertices dominating it (having an infinite fan to the ray) and the digraph has finitely many ends. The restriction to finitely many ends in (b) can be weakened, admitting infinitely many ends with a specific structure, but the possibility of dropping it remains a conjecture.     

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     

Disjoint quasi‐kernels in digraphs

A quasi‐kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question of which digraphs have a pair of disjoint quasi‐kernels. Clearly, a digraph has a pair of disjoint quasi‐kernels cannot contain sinks, that is, vertices of outdegree zero, as each such vertex is necessarily included in a quasi‐kernel. However, there exist digraphs which contain neither sinks nor a pair of disjoint quasi‐kernels. Thus, containing no sinks is not sufficient in general for a digraph to have a pair of disjoint quasi‐kernels. In contrast, we prove that, for several classes of digraphs, the condition of containing no sinks guarantees the existence of a pair of disjoint quasi‐kernels. The classes contain semicomplete multipartite, quasi‐transitive, and locally semicomplete digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:251‐260, 2008     

A sufficient condition for boundedness of tolerance graphs

Golumbic, Monma, and Trotter showed that every tolerance graph for which no vertex neighborhood is contained in another vertex neighborhood is a bounded tolerance graph. We strengthen this result by weakening the neighborhood condition. In this way, more tolerance graphs can be recognized as bounded. Our argument relies on a variation of the concept of “assertive vertices”.