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

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

The paired domination subdivision number of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the paired domination number of G. In this note, we show that the problem of computing the paired domination subdivision number is NP-hard for bipartite graphs. [ABSTRACT FROM AUTHOR]

A subset S of vertices in a graph G = (V, E) is 2-independent if every vertex of S has at most one neighbor in S. The 2-independence number is the maximum cardinality of a 2-independent set of G. In this paper, we initiate the study of the 2-independence subdivision number sdβ2 (G) defined as the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the 2-independence number. We first show that for every connected graph G of order at least three, 1 ≤ β2 (G) ≤ 2, and we give a necessary and sufficient condition for graphs G attaining each bound. Moreover, restricted to the class of trees, we provide a constructive characterization of all trees T with sdβ2(T) = 2, and we show that such a characterization suggests an algorithm that determines whether a tree T has β2 (T) = 2 or sd^2 (T) = 1 in polynomial time. [ABSTRACT FROM AUTHOR]

For a positive integer k, a subsetD of vertices in a digraph →G is a k-dominating set if every vertex not in D has at least k direct predecessors in D. The k-domination number is the minimum cardinality among all k-dominating sets of →G. The game k-domination number of a simple and undirected graph is defined by the following game. Two players, A and D, orient the edges of the graph alternately until all edges are oriented. Player D starts the game, and his goal is to decrease the k-domination number of the resulting digraph, while A is trying to increase it. The game k-domination number of the graph G is the kdomination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. We are mainly interested in the study of the game 2-domination number, where some upper bounds will be presented. We also establish a Nordhaus-Gaddum bound for the game 2-domination number of a graph and its complement. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G = (V;E) is a function f: V ! f0; 1; 2g such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. An RDF f is called an outer independent Roman dominating function (OIRDF) if the set of vertices assigned a 0 under f is an independent set. The weight of an OIRDF is the sum of its function values over all vertices, and the outer independent Roman domination number oiR(G) is the minimum weight of an OIRDF on G. In this paper, we show that if T is a tree of order n = 3 with s(T) support vertices, then oiR(T) minf 5n 6; 3n+s(T) 4 g: Moreover, we characterize the tress attaining each bound. [ABSTRACT FROM AUTHOR]

A domatic partition P of a graph G=(V,E) is a partition of V into classes that are pairwise disjoint dominating sets. Such a partition P is called b-maximal if no larger domatic partition P' can be obtained by gathering subsets of some classes of P to form a new class. The b-domatic number bd(G) is the minimum cardinality of a b-maximal domatic partition of G. In this paper, we characterize the graphs G of order n with bd(G) ∈ {n-1,n-2,n-3}. Then we prove that for any graph G on n vertices, bd(G)+bd(Ġ) ≤ n+1, where Ġ is the complement of G. Moreover, we provide a characterization of the graphs G of order n with bd(G)+bd(Ġ) ∈ {n+1,n} as well as those graphs for which bd(G)=bd(Ġ)=n/2. [ABSTRACT FROM AUTHOR]