The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D. The cyclic circulant tournament is denoted by [...] T=C→2n+1(1,2,…,n) $T={\overrightarrow{C}}_{2n+1}(1,2,...,n)$ , where V (T) = ℤ2n+1 and for every jump j ∈ 1, 2, . . . , n there exist the arcs (a, a + j) for every a ∈ ℤ2n+1. Consider the circulant tournament [...] C→2n+1〈k〉 ${\overrightarrow{C}}_{2n+1}〈k〉$ obtained from the cyclic tournament by reversing one...

For a vertex $v$ of a connected oriented graph $D$ and an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices of $D$, the (directed distance) representation of $v$ with respect to $W$ is the ordered $k$-tuple $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(v,w_i)$ is the directed distance from $v$ to $w_i$. The set $W$ is a resolving set for $D$ if every two distinct vertices of $D$ have distinct representations. The minimum cardinality of a resolving set for $D$ is the (directed distance) dimension $dim\left(D\right)$ of $D$. The dimension of a connected oriented graph need not be defined. Those oriented graphs...

By a ternary structure we mean an ordered pair $(U_0,T_0)$, where $U_0$ is a finite nonempty set and $T_0$ is a ternary relation on $U_0$. A ternary structure $(U_0,T_0)$ is called here a directed geodetic structure if there exists a strong digraph $D$ with the properties that $V\left(D\right)=U_0$ and $$T_0(u,v,w)\text{if}\text{and}\text{only}\text{if}{d}_D(u,v)+d_D(v,w)=d_D(u,w)$$ for all $u,v,w\in U_0$, where $d_D$ denotes the (directed) distance function in $D$. It is proved in this paper that there exists no sentence $𝐬$ of the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies...

The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.

For a finite commutative ring $R$ and a positive integer $k⩾2$, we construct an iteration digraph $G(R,k)$ whose vertex set is $R$ and for which there is a directed edge from $a\in R$ to $b\in R$ if $b=a^k$. Let $R=R_1\oplus ...\oplus R_s$, where $s>1$ and $R_i$ is a finite commutative local ring for $i\in \{1,...,s\}$. Let $N$ be a subset of $\{R_1,\cdots ,R_s\}$ (it is possible that $N$ is the empty set $\varnothing$). We define the fundamental constituents $G_N^{*}(R,k)$ of $G(R,k)$ induced by the vertices which are of the form $\{(a_1,\cdots ,a_s)\in R:a_i\in \mathrm{D}\left(R_i\right)$ if $R_i\in N$, otherwise $a_i\in \mathrm{U}\left(R_i\right),i=1,...,s\},$ where U$\left(R\right)$ denotes the unit group of $R$ and D$\left(R\right)$ denotes the zero-divisor set of $R$. We investigate...

Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF...

The problem of distinguishing, in terms of graph topology, digraphs with real and partially non-real Laplacian spectra is important for applications. Motivated by the question posed in [R. Agaev, P. Chebotarev, Which digraphs with rings structure are essentially cyclic?, Adv. in Appl. Math. 45 (2010), 232-251], in this paper we completely list the Laplacian eigenvalues of some digraphs obtained from the wheel digraph by deleting some arcs.

The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D(x) ∩ N+D(y) ≠ ∅ or N−D(x) ∩ N−D(y) ≠ ∅, where N+D(x) (resp. N−D(x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function f : V → R on the set V and a positive real number δ ∈ R such that (x, y) ∈ A if and only if...