An edge ordering of a graph G is an injection f : E(G) → R, the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent ; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of...

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by ${\gamma }_{\mathrm{pr}}\left(G\right)$, is the minimum cardinality of a paired-dominating set of $G$. The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of degree one,...

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.

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on...

Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]