We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large...

A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic...

We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan...

In the first part, we assign to each positive integer $n$ a digraph $\Gamma (n,5),$ whose set of vertices consists of elements of the ring ${\mathbb{Z}}_n=\{0,1,\cdots ,n-1\}$ with the addition and the multiplication operations modulo $n,$ and for which there is a directed edge from $a$ to $b$ if and only if $a^5\equiv b(modn)$. Associated with $\Gamma (n,5)$ are two disjoint subdigraphs: ${\Gamma }_1(n,5)$ and ${\Gamma }_2(n,5)$ whose union is $\Gamma (n,5).$ The vertices of ${\Gamma }_1(n,5)$ are coprime to $n,$ and the vertices of ${\Gamma }_2(n,5)$ are not coprime to $n.$ In this part, we study the structure of $\Gamma (n,5)$ in detail. In the second part, we investigate the zero-divisor...

For a nonempty set $S$ of vertices in a strong digraph $D$, the strong distance $d\left(S\right)$ is the minimum size of a strong subdigraph of $D$ containing the vertices of $S$. If $S$ contains $k$ vertices, then $d\left(S\right)$ is referred to as the $k$-strong distance of $S$. For an integer $k\ge 2$ and a vertex $v$ of a strong digraph $D$, the $k$-strong eccentricity ${\mathrm{s}e}_k\left(v\right)$ of $v$ is the maximum $k$-strong distance $d\left(S\right)$ among all sets $S$ of $k$ vertices in $D$ containing $v$. The minimum $k$-strong eccentricity among the vertices of $D$ is its $k$-strong radius ${\mathrm{s}rad}_{k}D$ and the maximum...

In this paper we derive necessary and sufficient conditions for the existence of kernels by monochromatic paths in the corona of digraphs. Using these results, we are able to prove the main result of this paper which provides necessary and sufficient conditions for the corona of digraphs to be monochromatic kernel-perfect. Moreover we calculate the total numbers of kernels by monochromatic paths, independent by monochromatic paths sets and dominating by monochromatic paths sets in this digraphs...

In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special...

In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.