Search

In this paper, we survey results on the Roman domatic number and its variants in both graphs and digraphs. This fifth survey completes our works on Roman domination and its variations published in two book chapters and two other surveys.

A perfect Italian dominating function (PIDF) on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that for every vertex u with f(u) = 0, the total weight of f assigned to the neighbors of u is exactly two. The weight of a PIDF is the sum of its functions values over all vertices. The perfect Italian domination number of G, denoted γIp(G)\gamma _I^p\left( G \right), is the minimum weight of a PIDF of G. In this paper, we show that for every tree T of order n ≥ 3, with ℓ(T) leaves and s(T) support vertices, γpI(T) ≤ γIp(T)≤4n-l(T)+2s(T-1)5\gamma _I^p\left( T \right) \le {{4n - \mathcal{l}\left( T \right) + 2s\left( {T - 1} \right)} \over 5}, improving a previous bound given by T.W. Haynes and M.A. Henning in [Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177].

A vertex v of a simple graph G = (V , E) ve-dominates every edge incident to v as well as every edge adjacent to these incident edges. A set D ⊆ V is a total vertex-edge dominating set if every edge of E is ve-dominated by a vertex of D and the subgraph induced by D has no isolated vertex. The total vertex-edge domination problem is to find a total vertex-edge dominating set of minimum cardinality. In this paper, we first show that the total vertex-edge domination problem is NP-complete for chordal graphs. Then we provide a linear-time algorithm for this problem in trees. Moreover, we show that the minimum total vertex-edge domination problem cannot be approximated within (1 −) ln | V | for any > 0 unless NP ⊆ DTIME (| V | O (log log | V |) ). Finally, we prove that the minimum total vertex-edge domination problem is APX-complete for bounded-degree graphs. [ABSTRACT FROM AUTHOR]

A subset K of vertices of digraph D = (V(D), A(D)) is a kernel if the following two conditions are fulfilled: (i) no two vertices of are connected by an arc in any direction and (ii) every vertex not in has an ingoing arc from some vertex in K. A quasi-kernel of D is a subset Q of vertices satisfying condition (i) and furthermore every vertex can be reached in at most two steps from Q. A vertex is source-free if it has at least one ingoing arc. In 1976, P.L. Erdös and L.A. Székely conjectured that every source-free digraph D has a quasi-kernel of size at most |V(D)| /2Recently, this conjecture has been shown to be true by Allan van Hulst for digraphs having kernels. In this note, we provide a short and simple proof of van Hulst's result. We additionally characterize all source-free digraphs D having kernels with smallest quasi-kernels of size |V (D)| /2. [ABSTRACT FROM AUTHOR]

Given a graph G with no isolated vertices, let γ e v (G) , i e v (G) , β e v (G) , γ (G) , γ pr (G) and Γ pr (G) denote the ev-domination number, the independent ev-domination number, the upper independent ev-domination number, the domination number, the paired-domination number and the upper paired-domination number, respectively. It is known that γ e v (G) = i e v (G) = 1 2 γ pr (G) ≤ β e v (G). In this paper, we extend this inequality chain to involve the upper paired-domination number for arbitrary graphs G with no isolated vertices as well as the domination number for trees. Moreover, we show that recognizing well ev-covered graphs (i.e., graphs G with i e v (G) = β e v (G)) is co-NP-complete, solving an open problem posed by Boutrig and Chellali. [ABSTRACT FROM AUTHOR]

A Roman dominating function on a graph G = (V, E) is a function f:V (G) → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value w(f) = Σu∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G) ≤ n + 1 − Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G) = n + 1 − Δ is co-𝒩 𝒫-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for γR(G) + γR (Ḡ), where Ḡ is the complement graph of G.

In this note, we address an open problem posed in [Boutrig, Chellali, Haynes and Hedetniemi, Vertex-edge domination in graphs. Aquaestiones Mathematicae 90 (2016) 355- 366] concerning the characterization of nontrivial trees T with equal independent ve-domination number ive(T) and domination number γ(T). We provide four equivalent conditions for trees T with ive (T) = γ(T) involving, among others, the domination number, the total domination number γt (T) and the ve-domination number γve (T). [ABSTRACT FROM AUTHOR]

In a graph G of minimum degree δ and maximum degree Δ, a subset S of vertices of G is j-independent, for some positive integer j; if every vertex in S has at most j - 1 neighbors in S. The j-independence number βj(G) is the maximum cardinality of a j-independent set of G. We first establish an inequality between βj(G) and βΔ(G) for 1 ≤ j ≤ δ-1. Then we characterize all graphs G with βj(G) = βΔ(G) for j ∈ {1,...,Δ-1}, where the particular cases j = 1, 2, δ-1 and δ are well distinguished. [ABSTRACT FROM AUTHOR]

A restrained {2}-dominating function (R{2}DF) on a graph G = (V, E) is a function f : V → {0, 1, 2} such that : (i) f(N[v]) ≥ 2 for all v ∈ V, where N[v] is the set containing v and all vertices adjacent to v; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an R{2}DF is the sum of its function values over all vertices, and the restrained {2}-domination number γr{2}(G) is the minimum weight of an R{2}DF on G. In this paper, we initiate the study of the restrained {2}-domination number. We first prove that the problem of computing this parameter is NP-complete, even when restricted to bipartite graphs. Then we give various bounds on this parameter. In particular, we establish upper and lower bounds on the restrained {2}-domination number of a tree T in terms of the order, the numbers of leaves and support vertices. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).

An edge in a graph G = (V, E) is said to ev-dominate the vertices incident to it as well as the vertices adjacent to these incident vertices. A subset F ⊆ E is an edge-vertex dominating set (or simply, ev-dominating set) if every vertex is ev-dominated by at least one edge of F. The ev-domination number γev(G) is the minimum cardinality of a ev-dominating set of G. An ev-dominating set is independent if its edges are independent. The independent ev-domination number iev(G) is the minimum cardinality of an independent ev-dominating set and the upper independent ev-domination number βev(G) is the maximum cardinality of a minimal independent ev-dominating set of G. In this paper, we show that for every nontrivial tree T, γev(T) = iev(T) ≤ γ(T) ≤ βev(T), where γ(T) is the domination number of T. Moreover, we provide a characterization of all trees T with iev(T) = βev(T), which we call well ev-covered trees, as well as a characterization of all trees T with γev(T) = iev(T) = γ(T). [ABSTRACT FROM AUTHOR]

An independent Roman dominating function (IRD-function) on a graph G is a function f : V(G) → {0, 1, 2} satisfying the conditions that (i) every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) the set of all vertices assigned non-zero values under f is independent. The weight of an IRD-function is the sum of its function values over all vertices, and the independent Roman domination number iR(G) of G is the minimum weight of an IRD-function on G. In this paper, we initiate the study of the independent Roman bondage number biR(G) of a graph G having at least one component of order at least three, defined as the smallest size of set of edges F ⊆ E(G) for which iR(G − F) > iR(G). We begin by showing that the decision problem associated with the independent Roman bondage problem is NP-hard for bipartite graphs. Then various upper bounds on biR(G) are established as well as exact values on it for some special graphs. In particular, for trees T of order at least three, it is shown that biR(T) ≤ 3, while for connected planar graphs the upper bounds are in terms of the maximum degree with refinements depending on the girth of the graph. [ABSTRACT FROM AUTHOR]