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

Homotopic methods are employed for the characterization of the complete digraphs which are the composition of non-trivial highly regular tournaments.

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted...

In this note, we show how the determinant of the q-distance matrix Dq(T) of a weighted directed graph G can be expressed in terms of the corresponding determinants for the blocks of G, and thus generalize the results obtained by Graham et al. [R.L. Graham, A.J. Hoffman and H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977) 85-88]. Further, by means of the result, we determine the determinant of the q-distance matrix of the graph obtained from a connected weighted graph...

Let (−→ Cm2−→ Cn) be the domination number of the Cartesian product of directed cycles −→ Cm and −→ Cn for m, n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of (−→ Cm2−→ Cn) when m ≤ 6 and [12] when both m and n ≡ 0(mod 3). In this article we give, in general, the value of (−→ Cm2−→ Cn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].

Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k, l)-kernel N of D is a k-independent (if u, v ∈ N, u 6= v, then d(u, v), d(v, u) ≥ k) and l-absorbent (if u ∈ V (D) − N then there exists v ∈ N such that d(u, v) ≤ l) set of vertices. A k-kernel is a (k, k −1)-kernel. This work is a survey of results proving sufficient conditions for the existence of (k, l)-kernels in infinite digraphs. Despite all the previous work in this direction was done for...

A power digraph, denoted by $G(n,k)$, is a directed graph with ${\mathbb{Z}}_n=\{0,1,\cdots ,n-1\}$ as the set of vertices and $E=\{(a,b):a^k\equiv b(modn)\}$ as the edge set. In this paper we extend the work done by Lawrence Somer and Michal Křížek: On a connection of number theory with graph theory, Czech. Math. J. 54 (2004), 465–485, and Lawrence Somer and Michal Křížek: Structure of digraphs associated with quadratic congruences with composite moduli, Discrete Math. 306 (2006), 2174–2185. The heights of the vertices and the components of $G(n,k)$ for $n\ge 1$ and $k\ge 2$ are determined....

The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n,s}$ be the oriented graph such that $V\left(D_{n,s}\right)$ is the set of integers mod 2n+1 and $A\left(D_{n,s}\right)=(i,j):j-i\in 1,2,...,n\setminus s..$In this paper we prove that $hc\left(D_{n,s}\right)\le 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

In this note, we give an easy and short proof for the theorem by Park and Kim stating that the hypercompetition numbers of hypergraphs with maximum degree at most two is at most two.