Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...

We define digraphs minimal, critical, and maximal by three types of radii. Some of these classes are completely characterized, while for the others it is shown that they are large in terms of induced subgraphs.

The paper gives an overview of results for radially minimal, critical, maximal and stable graphs and digraphs.

We assign to each pair of positive integers $n$ and $k\ge 2$ a digraph $G(n,k)$ whose set of vertices is $H=\{0,1,\cdots ,n-1\}$ and for which there is a directed edge from $a\in H$ to $b\in H$ if $a^k\equiv b(modn)$. The digraph $G(n,k)$ is semiregular if there exists a positive integer $d$ such that each vertex of the digraph has indegree $d$ or 0. Generalizing earlier results of the authors for the case in which $k=2$, we characterize all semiregular digraphs $G(n,k)$ when $k\ge 2$ is arbitrary.

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n/d\rceil$. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that ${\alpha }_0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least ${\alpha }_{0}n$ contains a directed triangle. Let $ϵ<(3-2{\alpha }_0)/(4-2{\alpha }_0)$ be a positive real. We show that if $D$ is an oriented graph without...

In the present paper we generalize a few algebraic concepts to graphs. Applying this graph language we solve some problems on subalgebra lattices of unary partial algebras. In this paper three such problems are solved, other will be solved in papers [Pió I], [Pió II], [Pió III], [Pió IV]. More precisely, in the present paper first another proof of the following algebraic result from [Bar1] is given: for two unary partial algebras $𝐀$ and $𝐁$, their weak subalgebra lattices are isomorphic if and only...

The (directed) distance from a vertex $u$ to a vertex $v$ in a strong digraph $D$ is the length of a shortest $u$-$v$ (directed) path in $D$. The eccentricity of a vertex $v$ of $D$ is the distance from $v$ to a vertex furthest from $v$ in $D$. The radius rad$D$ is the minimum eccentricity among the vertices of $D$ and the diameter diam$D$ is the maximum eccentricity. A central vertex is a vertex with eccentricity $\mathrm{r}adD$ and the subdigraph induced by the central vertices is the center $C\left(D\right)$. For a central vertex $v$ in a strong digraph...

One of the main aims of the present and the next part [15] is to show that the theory of graphs (its language and results) can be very useful in algebraic investigations. We characterize, in terms of isomorphisms of some digraphs, all pairs $\langle 𝐀,𝐋\rangle$, where $𝐀$ is a finite unary algebra and $L$ a finite lattice such that the subalgebra lattice of $𝐀$ is isomorphic to $𝐋$. Moreover, we find necessary and sufficient conditions for two arbitrary finite unary algebras to have isomorphic subalgebra lattices. We solve...

We use graph-algebraic results proved in [8] and some results of the graph theory to characterize all pairs $\langle {𝐋}_1,{𝐋}_2\rangle$ of lattices for which there is a finite partial unary algebra such that its weak and strong subalgebra lattices are isomorphic to ${𝐋}_1$ and ${𝐋}_2$, respectively. Next, we describe other pairs of subalgebra lattices (weak and relative, etc.) of a finite unary algebra. Finally, necessary and sufficient conditions are found for quadruples $\langle {𝐋}_1,{𝐋}_2,{𝐋}_3,{𝐋}_4\rangle$ of lattices for which there is a finite unary algebra having...