On the existence of 3- and 4-kernels in digraphs

Let $D=(V\left(D\right),A\left(D\right))$ be a digraph. A subset $S?V\left(D\right)$ is $k$-independent if the distance between every pair of vertices of $S$ is at least $k$, and it is $?$-absorbent if for every vertex $u$ in $V\left(D\right)?S$ there exists $v\in S$ such that the distance from $u$ to $v$ is less than or equal to $?$. A $k$-kernel is a $k$-independent and $(k?1)$-absorbent set. A kernel is simply a $2$-kernel.A classical result due to Duchet states that if every directed cycle in a digraph $D$ has at least one symmetric arc, then $D$ has a kernel. We propose a conjecture generalizing this result for $k$-kernels and prove it true for $k=3$ and $k=4$.     

Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph D with real-valued vertex costs, find, for each j=1,2,…,|V(D)|, j disjoint paths P₁,P₂,…,P_j such that the total cost of these paths is minimum among all collections of j disjoint paths in D.     

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.     

Kernels by properly colored paths in arc-colored digraphs

A kernel by properly colored paths of an arc-colored digraph $D$ is a set $S$ of vertices of $D$ such that (i) no two vertices of $S$ are connected by a properly colored directed path in $D$, and (ii) every vertex outside $S$ can reach $S$ by a properly colored directed path in $D$. In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given.     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈N, there is no monochromatic directed path between them, and (ii) 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 prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

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 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.     

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

We call the tournament T an m-coloured tournament if the arcs of T are coloured with m-colours. If v is a vertex of an m-coloured tournament T, we denote by ξ(v) the set of colours assigned to the arcs with v as an endpoint. In this paper is proved that if T is an m-coloured tournament with |ξ(v)|≤2 for each vertex v of T, and T satisfies at least one of the two following properties (1) m≠3 or (2) m=3 and T contains no C₃ (the directed cycle of length 3 whose arcs are coloured with three distinct colours). Then there is a vertex v of T such that for every other vertex x of T, there is a monochromatic directed path from x to v. Received: April, 2003     

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.     

Cliques that are tolerance digraphs

In this paper, we study directed graph versions of tolerance graphs, in particular, the class of totally bounded bitolerance digraphs and several subclasses. When the underlying graph is complete, we prove that the classes of totally bounded bitolerance digraphs and interval catch digraphs are equal, and this implies a polynomial-time recognition algorithm for the former class. In addition, we give examples (whose underlying graphs are complete) to separate every other pair of subclasses, and one of these provides a counterexample to a conjecture of Maehara (1984).     

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

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.     

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.     

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     

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.