A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Roman Domination Dot-critical Graphs

A Roman dominating function on a graph G is a function f : V(G) → {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 a Roman dominating function is the value ${f(V(G))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.     

Unique response Roman domination in graphs

A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V₀,V₁,V₂) of V(G), where V_i={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V₀ implies |N(x)∩V₂|≤1 and x∈V₁∪V₂ implies that |N(x)∩V₂|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by u_R(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

Characterizations of trees with equal domination parameters

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set, if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a restrained dominating set of G. A set S ⊆ V is a weak dominating set of G if, for every u in V − S, there exists a v ∈ S such that uv ∈ E and deg u ≥ deg v. The weak domination number of G, denoted by γ_w(G), is the minimum cardinality of a weak dominating set of G. In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 142–153, 2000     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G is a function f : V(G) → {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 a Roman dominating function is the value f (V(G)) = ?_{u ? V(G)} f (u){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.     

On the bondage number of middle graphs

Let G = (V (G),E(G)) be a simple graph. A subset S of V (G) is a dominating set of G if, for any vertex v ∈ V (G) — S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimal dominating set of G. There are several types of domination parameters depending upon the nature of domination and the nature of dominating set. These parameters are bondage, reinforcement, strong-weak domination, strong-weak bondage numbers. In this paper, we first investigate the strong-weak domination number of middle graphs of a graph. Then several results for the bondage, strong-weak bondage number of middle graphs are obtained.     

An upper bound for domination number of 5-regular graphs

Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n.     

Matching Properties in Total Domination Vertex Critical Graphs

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

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

Roman dominating influence parameters

A function f:V(G)→{0,1,2} is a Roman dominating function for a graph G=(V,E) if for every vertex v with f(v)=0, there exists a vertex w∈N(v) with f(w)=2. Emperor Constantine had the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and traveling. Each vertex with no army must have a neighboring vertex with a traveling army. Stationary armies then dominate their own vertices, and a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the traveling army. In this paper, we introduce Roman dominating influence parameters in which the interest is in dominating each vertex exactly once.     

Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

Efficient algorithms for Roman domination on some classes of graphs

A Roman dominating function of a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=∑_x∈Vf(x), and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of -free graphs and graphs with a d-octopus.     

On equality in an upper bound for the restrained and total domination numbers of a graph

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_t(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γ_r(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γ_t(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γ_t(G)=n-Δ.     

Dominating Sets of Some Graphs Associated to Commutative Rings

Let G = (V, E) be a graph. A set S ? V is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this article is to study and characterize the dominating sets of the zero-divisor graph Γ(R) and ideal-based zero-divisor graph Γ _I (R) of a commutative ring R.     

Regular graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that regular graphs and graphs with γ=4 are not universal fixers.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Domination critical graphs

A set of vertices S is said to dominate the graph G if for each v ? S, there is a vertex u ∈ S with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, u ∈ V(G) with v not adjacent to u, γ(G + vu) < γ(G). Thus G is k-y-critical if γ(G) = k and for each edge e ? E(G), γ(G + e) = k ?1. The 2-domination critical graphs are characterized the properties of the k-critical graphs with k ≥ 3 are studied. In particular, the connected 3-critical graphs of even order are shown to have a 1-factor and some stringent restrictions on their degree sequences and diameters are obtained.