Signed total Roman domination in graphs

Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A signed total Roman dominating function (STRDF) on a graph \(G\) is a function \(f:V(G)\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{x\in N(v)}f(x)\ge 1\) for each vertex \(v\in V(G)\), where \(N(v)\) is the neighborhood of \(v\), and (ii) every vertex \(u\) for which \(f(u)=-1\) is adjacent to at least one vertex \(v\) for which \(f(v)=2\). The weight of an SRTDF \(f\) is \(\sum _{v\in V(G)}f(v)\). The signed total Roman domination number \(\gamma _{stR}(G)\) of \(G\) is the minimum weight of an STRDF on \(G\). In this paper we initiate the study of the signed total Roman domination number of graphs, and we present different bounds on \(\gamma _{stR}(G)\). In addition, we determine the signed total Roman domination number of some classes of graphs.     

Signed mixed Roman domination numbers in graphs

Let \(G = (V;E)\) be a simple graph with vertex set \(V\) and edge set \(E\). A signed mixed Roman dominating function (SMRDF) of \(G\) is a function \(f: V\cup E\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{y\in N_m[x]}f(y)\ge 1\) for each \(x\in V\cup E\), where \(N_m[x]\) is the set, called mixed closed neighborhood of \(x\), consists of \(x\) and the elements of \(V\cup E\) adjacent or incident to \(x\) (ii) every element \(x\in V\cup E\) for which \(f(x) = -1\) is adjacent or incident to at least one element \(y\in V\cup E\) for which \(f(y) = 2\). The weight of a SMRDF \(f\) is \(\omega (f)=\sum _{x\in V\cup E}f(x)\). The signed mixed Roman domination number \(\gamma _{sR}^*(G)\) of \(G\) is the minimum weight of a SMRDF of \(G\). In this paper we initiate the study of the signed mixed Roman domination number and we present bounds for this parameter. In particular, we determine this parameter for some classes of graphs.     

Roman domination on strongly chordal graphs

Given real numbers b≥a>0, an (a,b)-Roman dominating function of a graph G=(V,E) is a function f:V→{0,a,b} such that every vertex v with f(v)=0 has a neighbor u with f(u)=b. An independent/connected/total (a,b)-Roman dominating function is an (a,b)-Roman dominating function f such that {v∈V:f(v)≠0} induces a subgraph without edges/that is connected/without isolated vertices. For a weight function $w{:} V\to\Bbb{R}$ , the weight of f is w(f)=∑ _v∈V w(v)f(v). The weighted (a,b)-Roman domination number $\gamma^{(a,b)}_{R}(G,w)$ is the minimum weight of an (a,b)-Roman dominating function of G. Similarly, we can define the weighted independent (a,b)-Roman domination number $\gamma^{(a,b)}_{Ri}(G,w)$ . In this paper, we first prove that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/independent (a,b)-Roman domination problems are NP-complete for bipartite graphs. We also show that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/weighted independent (a,b)-Roman domination problems are NP-complete for chordal graphs. We then give linear-time algorithms for the weighted (a,b)-Roman domination problem with b≥a>0, and the weighted independent (a,b)-Roman domination problem with 2a≥b≥a>0 on strongly chordal graphs with a strong elimination ordering provided.     

Restricted domination parameters in graphs

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ _m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r _k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r _k (G,γ _m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r _k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r _k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Disjunctive total domination in graphs

Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, \(\gamma _t(G)\). A set \(S\) of vertices in \(G\) is a disjunctive total dominating set of \(G\) if every vertex is adjacent to a vertex of \(S\) or has at least two vertices in \(S\) at distance \(2\) from it. The disjunctive total domination number, \(\gamma ^d_t(G)\), is the minimum cardinality of such a set. We observe that \(\gamma ^d_t(G) \le \gamma _t(G)\). We prove that if \(G\) is a connected graph of order \(n \ge 8\), then \(\gamma ^d_t(G) \le 2(n-1)/3\) and we characterize the extremal graphs. It is known that if \(G\) is a connected claw-free graph of order \(n\), then \(\gamma _t(G) \le 2n/3\) and this upper bound is tight for arbitrarily large \(n\). We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if \(G\) is a connected claw-free graph of order \(n > 14\), then \(\gamma ^d_t(G) \le 4n/7\) and we characterize the graphs achieving equality in this bound.     

Paired domination versus domination and packing number in graphs

Journal of Combinatorial Optimization - Given a graph $$G=(V(G), E(G))$$ , the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are...     

Restrained domination in cubic graphs

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then g_r(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then g_r(G) ￡ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ _r (G)=γ(G).     

Independent domination in subcubic graphs

Journal of Combinatorial Optimization - A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in&nbsp;S. If, in addition, S is an independent...     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

Total restrained domination in claw-free graphs

A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ _tr (G)=n. Also, we show that γ _tr (G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.     

Roman game domination number of a graph

The Roman game domination number of an undirected graph G is defined by the following game. Players \(\mathcal {A}\) and \(\mathcal {D}\) orient the edges of the graph G alternately, with \(\mathcal {D}\) playing first, until all edges are oriented. Player \(\mathcal {D}\) (frequently called Dominator) tries to minimize the Roman domination number of the resulting digraph, while player \(\mathcal {A}\) (Avoider) tries to maximize it. This game gives a unique number depending only on G, if we suppose that both \(\mathcal {A}\) and \(\mathcal {D}\) play according to their optimal strategies. This number is called the Roman game domination number of G and is denoted by \(\gamma _{Rg}(G)\). In this paper we initiate the study of the Roman game domination number of a graph and we establish some bounds on \(\gamma _{Rg}(G)\). We also determine the Roman game domination number for some classes of graphs.     

On the outer-connected domination in graphs

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if δ(G)≥2 and diam?(G)≤2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.     

Edge lifting and total domination in graphs

Let u and v be vertices of a graph G, such that the distance between u and v is two and x is a common neighbor of u and v. We define the edge lift of uv off x as the process of removing edges ux and vx while adding the edge uv to G. In this paper, we investigate the effect that edge lifting has on the total domination number of a graph. Among other results, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. Trees for which every possible edge lift increases the total domination number are characterized.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.     

Perfect matchings in paired domination vertex critical graphs

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired dominating set of?G. A?graph with no isolated vertex is called paired domination vertex critical, or briefly γ _pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ _pr (G?v)<γ _pr (G). A?γ _pr -critical graph G is said to be k-γ _pr -critical if γ _pr (G)=k. In this paper, we firstly show that every 4-γ _pr -critical graph of even order has a perfect matching if it is K _1,5-free and every 4-γ _pr -critical graph of odd order is factor-critical if it is K _1,5-free. Secondly, we show that every 6-γ _pr -critical graph of even order has a perfect matching if it is K _1,4-free.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

An upper bound on the double Roman domination number

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) is a function \(f : V \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\), and if \(f(v)=1\), then vertex v must have at least one neighbor w with \(f(w)\ge 2\). The weight of a DRDF f is the value \(f(V) = \sum _{u \in V}f(u)\). The double Roman domination number \(\gamma _{dR}(G)\) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality \(\gamma _{dR}(G)\le \frac{6n}{5}\) and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, \(\gamma _{dR}(G)\le \frac{8n}{7}\).