The Roman domination numberγR(G) ofGis the minimum of Σv∈V(G)f(v) over such functions

research paper

BOUNDS ON ROMAN DOMINATION NUMBERS OF GRAPHS B.P. Mobaraky and S.M. Sheikholeslami

Abstract. Roman dominating function of a graphGis a labeling function f:V(G) → {0,1,2}such that every vertex with label 0 has a neighbor with label 2. The Roman domination numberγR(G) ofGis the minimum of Σv∈V(G)f(v) over such functions. In this paper, we find lower and upper bounds for Roman domination numbers in terms of the diameter and the girth ofG.

1. Introduction

ForG, a simple graph with vertex setV(G) and edge setE(G) (brieflyV and E), theopen neighborhood N(v) of the vertexv is the set{u∈V(G)|uv∈E(G)}

and itsclosed neighborhoodisN[v] =N(v)∪ {v}. Similarly, theopen neighborhood of a set S ⊆ V is the set N(S) = S

v∈SN(v), and its closed neighborhood is N[S] =N(S)∪S. The minimum and maximum vertex degrees inGare denoted by δ(G) and ∆(G), respectively. A subset S of vertices of G is a dominating set ifN[S] = V. Thedomination number γ(G) is the minimum cardinality of a dominating set ofG. A subset S of vertices ofGis a2-packing if for each pair of verticesu, v∈S,N[u]∩N[v] =∅.

ARoman dominating function(RDF) on a graphG= (V, E) is defined in [13], [15] as a functionf:V −→ {0,1,2} satisfying the condition that a vertex v with f(v) = 0 is adjacent to at least one vertexuwithf(u) = 2. Theweightof a RDF is defined as w(f) = P

v∈V f(v). The Roman domination number of a graph G, denoted byγR(G), equals the minimum weight of a RDF on G. A γR(G)-function is a Roman dominating function of Gwith weightγR(G). Observe that a Roman dominating function f: V → {0,1,2} can be presented by an ordered partition (V0, V1, V2) ofV, where Vi={v∈V |f(v) =i}.

Cockayne et. al [3] initiated the study of Roman domination, suggested orig- inally in a Scientific American article by Ian Stewart [15]. Since V1 ∪V2 is a dominating set when f is a RDF, and since placing weight 2 at the vertices of a dominating set yields a RDF, they observed that

γ(G)≤γR(G)≤2γ(G). (1)

AMS Subject Classification: 05C69, 05C05.

Keywords and phrases: Roman domination number, diameter, girth.

247

In a sense, 2γ(G)−γR(G) measures “inefficiency” of domination, since the vertices with weight 1 in a RDF serve only to dominate themselves. The authors [3] in- vestigated graph theoretic properties of RDFs and characterizedγR(G) for specific graphs. They found out the graphsG, those withγR(G) =γ(G) +kwhen k≤2;

and then for largerkby Xing et al. [16]. They also characterized the graphsGwith propertyγR(G) = 2γ(G) in terms of 2-packings, referring them to asRomangraphs.

Henning [9] characterized Roman trees, while Song and Wang [14] identified the treesT withγR(T) =γ(T) + 3. Computational complexity ofγR(G) is considered in [4]. In [12], linear-time algorithms are given forγR(G) on interval graphs and on cographs, along with a polynomial-time algorithm for AT-free graphs. Chambers et al. [2] proved thatγR(G)≤ ⁴ⁿ₅ whenGis a connected graph of ordern≥3, and determined when equality holds. They have also obtained sharp upper and lower bounds forγR(G) +γR(G) andγR(G)γR(G), where Gdenotes the complement of G. Favaron et al. [7] proved thatγR(G) +^γ(G)₂ ≤nfor any connected graphGof ordern≥3. Other related domination models are studied in [1, 5, 6, 10, 11].

The purpose of this paper is to establish sharp lower and upper bounds for Roman domination numbers in terms of the diameter and the girth ofG.

Cockayne et al. in [3] proved that:

Theorem A.For a graph G of ordern,

γ(G)≤γR(G)≤2γ(G), with equality in lower bound if and only ifG=Kn.

Theorem B.For paths Pn and cyclesCn,

γR(Pn) =γR(Cn) =

»2n 3

¼ .

Theorem C.Let G=Km1,... ,mn be the complete n-partite graph with m1 ≤ m2≤. . .≤mn. If m1= 2, thenγR(G) = 3.

Theorem D. Let f = (V₀^f, V₁^f, V₂^f) be a γR-function for a simple graph G, such that |V₁^f| is minimum. Then V₁^f is a 2-packing.

2. Bounds in terms of the diameter

In this section sharp lower and upper bounds forγR(G) in terms of diam (G) are presented. Recall that theeccentricityof vertexvisecc(v) = max{d(v, w) :w∈V} and thediameterof G is diam (G) = max{ecc(v) :v∈V}. Throughout this section we assume thatGis a nontrivial graph of ordern≥2.

Theorem 1. If a graphGhas diameter two, thenγR(G)≤2δ. Furthermore, this bound is sharp for infinite family of graphs.

Proof. Since G has diameter two, N(u) dominates V(G) for all vertex u ∈ V(G). Now, let u ∈ V(G) and deg(u) = δ. Define f: V(G) −→ {0,1,2} by f(x) = 2 forx∈N(u) andf(x) = 0 otherwise. Obviouslyf is a RDF ofG. Thus γR(G)≤2δ.

To prove sharpness, letGbe obtained from Cartesian productP2¤Km(m≥ 3) by adding a new vertexxand jointing it to exactly one vertex at each copy of Km. Obviously, diam (G) = 2 and γR(G) = 4 = 2δ. This completes the proof.

Next theorem presents a lower bound for Roman domination numbers in terms of the diameter.

Theorem 2. For a connected graph G, γR(G)≥

»diam (G) + 2 2

¼ .

Furthermore, this bound is sharp forP3 andP4.

Proof. The statement is obviously true for K2. Let Gbe a connected graph of order n ≥ 3 and f = (V₀^f, V₁^f, V₂^f) be a γR(G)-function. Suppose that P = v1v2. . . v_{diam (G)+1} is a diametral path inG. This diametral path includes at most two edges from the induced subgraph G[N[v]] for each v ∈ V₁^f ∪V₂^f. Let E⁰ = {v_iv_i+1 | 1 ≤ i ≤ diam (G)} ∩S

v∈V₁^f∪V₂^fE(G[N[v]]). Then the diametral path contains at most|V₂^f| −1 edges not inE⁰, joining the neighborhoods of the vertices ofV₂^f. SinceGis a connected graph of order at least 3,V₂^f 6=∅. Hence,

diam (G)≤2|V₂^f|+ 2|V₁^f|+ (|V₂^f| −1)≤2γR(G)−2, and the result follows.

In the following theorem, an upper bound is presented for Roman domination numbers.

Theorem 3. For any connected graph Gon nvertices, γR(G)≤n−

¹1 + diam (G) 3

º .

Furthermore, this bound is sharp.

Proof. Let P = v1v2. . . vdiam (G)+1 be a diametral path in G. Moreover, let f = (V₀^f, V₁^f, V₂^f) be a γR(P)-function. By Theorem B, the weight of f is d2diam (G)+2

3 e. Define g:V(G) −→ {0,1,2} by g(x) = f(x) for x ∈ V(P) and g(x) = 1 forx∈V(G)\V(P). Obviouslygis a RDF forG. Hence,

γR(G)≤w(f) + (n−diam (G)−1) =n−

¹1 + diam (G) 3

º .

To prove sharpness, let G be obtained from a path P = v1v2. . . v3k (k ≥ 2) by adding a pendant edge v3u. Obviously, G achieves the bound and the proof is complete.

For a connected graphGwithδ≥3, the bound in Theorem 3 can be improved as follows.

Theorem 4. For any connected graph Gof ordern withδ≥3, γR(G)≤n−

¹1 + diam (G) 3

º

−(δ−2)

¹diam (G) + 2 3

º .

Proof. Let P = v1v2. . . vdiam (G)+1 be a diametral path in G and f = (V₀^f, V₁^f, V₂^f) be a γR(P)-function for which |V₁^f| is minimized and V₂^f is a 2- packing. Obviously, |V₂^f| = b^{diam (G)+2}₃ c. Let V₂^f = {u1, . . . , uk} where k = b^{diam (G)+2}₃ c. SincePis a diametral path, each vertex ofV₂^fhas at leastδ−2 neigh- bors inV(G)\V(P) andN(ui)∩N(uj) =∅ifui 6=uj. Defineg:V(G)−→ {0,1,2}

byg(x) =f(x) forx∈V(P), g(x) = 0 forx∈S_k

i=1N(ui)∩(V(G)\V(P)) and g(x) = 1 whenx∈V(G)\(V(P)∪(S_k

i=1N(ui))). Obviouslygis a RDF forGand so

γR(G)≤w(g) =w(f) +n−diam (G)−1−(δ−2)

¹diam (G) + 2 3

º . Now the result follows fromw(f) =d2diam (G)+2

3 e.

The next theorem speaks of an interesting relationship between the diameter ofGand the Roman domination number ofG, the complement of G.

Theorem 5. For a connected graph Gwithdiam (G)≥3,γR(G)≤4.

Proof. Let P = v1v2. . . vm be a diametral path in G where m ≥ 4. Let S ={v1, vm}. Since diam (G) ≥3, each vertex v ∈ V(G)\S can be adjacent to at most one vertex ofS in G. Consequently,S is a dominating set forG. By (1), γR(G)≤2γ(G)≤4 and the proof is complete.

3. Bounds in terms of the girth

In this section we present bounds on Roman domination numbers of a graph Gcontaining cycles, in terms of its girth. Recall that the girth of G (denoted by g(G)) is the length of a smallest cycle in G. Throughout this section, we assume thatGis a nontrivial graph of ordern≥3 and contains a cycle.

The following result is very crucial for this section.

Lemma 6. For a graphGof order nwithg(G)≥3we haveγR(G)≥ d^2g(G)₃ e.

Proof. First note that if Gis ann-cycle then γR(G) =d²ⁿ₃ eby Theorem B.

Now, letCbe a cycle of lengthg(G) inG. Ifg(G) = 3 or 4, then we need at least 1 or 2 vertices, respectively, to dominate the vertices ofCand the statement follows by Theorem A. Letg(G)≥5. Then a vertex not in V(C), can be adjacent to at most one vertex ofCfor otherwise we obtain a cycle of length less thang(G) which is a contradiction. Now the result follows by Theorem A.

Theorem 7. If g(G) = 4, thenγR(G)≥3. Equality holds if and only ifG is a bipartite graph with partite setsX andY with |X|= 2, where X has one vertex of degreen−2 and the other of degree at least two.

Proof. Letg(G) = 4. ThenγR(G)≥3 by Lemma 6. IfGis a bipartite graph satisfying the conditions, then obviously g(G) = 4 and γR(G) = 3 by Theorem C. Now letg(G) = 4 andγR(G) = 3 and f = (V₀^f, V₁^f, V₂^f) be a γR(G)-function.

Obviously,|V₁^f|=|V₂^f|= 1. Suppose thatV₁^f ={u}andV₂^f ={v}. SinceγR(G) = 3, {u, v} is an independent set andv is adjacent to all vertices in V(G)\ {u, v}.

Let X = {u, v} and Y = V(G)\X. Since g(G) = 4, Y is an independent set.

Henceforth,uandvare contained in each 4-cycle ofG. It follows thatuhas degree at least two. This completes the proof.

Theorem 8. Let G be a simple connected graph of order n, δ(G) ≥ 2 and g(G)≥5. Then γR(G)≤n− b^g(G)₃ c. Furthermore, the bound is sharp for cycles Cn with n≥5.

Proof. LetGbe such a graph. AssumeC is a cycle of Gwithg(G) edges. If G=C, then the statement is valid by Theorem B. Now letG⁰ be obtained from G by removing the vertices ofV(C). Sinceg(G)≥5, each vertex ofG⁰can be adjacent to at most one vertex ofCwhich impliesδ(G⁰)≥1. Thus,γR(G⁰)≤n−g(G). Let f andgbe aγR(G⁰)-function andγR(C)-function, respectively. Defineh:V(G)→ {0,1,2} byh(v) =f(v) forv∈V(G⁰) andh(v) =g(v) forv∈V(C). Obviously,h is a RDF ofGand the result follows.

Theorem 9. For a simple connected graph G of order n, if g(G) ≥5, then γR(G)≥2δ. The bound is sharp forC5 andC6.

Proof. Letf = (V₀^f, V₁^f, V₂^f) be a γR(G)-function such that|V₁^f|is minimum and let C be a cycle withg(G) edges. If n= 5, thenGis a 5-cycle and γ_R(G) = 4 = 2δ. For n ≥ 6, if δ ≤ 2, then γR(G) ≥ d^2g(G)₃ e ≥ 2δ by Lemma 6. Now, letδ ≥3. First suppose that V₁^f =∅. Assume v ∈V₀^f and N(v) ={v1, . . . , vk} for somek≥δ. Without loss of generality, one may suppose v1, . . . , vr∈V₂^f and vr+1, . . . , vk∈V₀^f and forj=r+ 1, . . . , k,vjv_j⁰ ∈E(G) wherev_j⁰ ∈V₂^f andk > r.

Sinceg(G)≥5, the vertices of v1, . . . , vr, v_r+1⁰ , . . . , v_k⁰ are distinct. Consequently,

|V₂^f| ≥ 2k which implies γR(G) ≥ 2k ≥ 2δ. For the case V1 6= ∅, by definition of f,|V₁^f| is an independent set. Suppose that u∈ V₁^f and N(u) ={u1, . . . , uk} for somek ≥δ. Obviously, N(u)⊆V₀^f. For eachj = 1, . . . , k, one may consider ujvj ∈E(G) wherevj ∈V₂^f. Since g(G)≥5, the verticesv1, . . . , vk are distinct.

Hence,γR(G) = 2|V₂^f|+|V₁^f| ≥2δ+ 1 and the proof is complete.

Theorem 10. For a simple connected graph G with δ ≥ 2 and g(G) ≥ 6, γR(G)≥4(δ−1). This bound is sharp forC6.

Proof. Letf = (V₀^f, V₁^f, V₂^f) be aγR(G)-function such that|V₁^f|is minimum.

Therefore, V₁^f is an independent set and N(w1)∩N(w2) = ∅ if w1 6= w2 for

w1, w2 ∈V₁^f. For V₁^f 6=∅ and u∈V₁^f, N(u) ={u1, . . . , udeg(u)} ⊆V₀^f. Suppose thatN(u1) ={w1, . . . , wr}whereu=w1. Sinceg(G)≥6,N(u)∩N(u1) =∅and N(ui)∩N(wj) = ∅ for each i, j. In this way, each vertex ofV₂^f can be adjacent to at most one vertex in (N(u)∪N(u1))∩V₀^f. This implies that |V₂^f| ≥2(δ−1) which follows the statement.

For V₁^f = ∅, |V₀^f| ≥ 2 holds clearly. If G[V₀^f] has an edge uv, analogous reasoning proves the statement. LetV₀^f be an independent set inGwith|V₀^f| ≥2 and u, v ∈V₀^f. Since g(G)≥6 and V₀^f is an independent set, |N(u)∩N(v)| ≤1 andN(u)∪N(v)⊆V₂^f. This implies that|V₂^f| ≥2δ−1 and the result follows.

Theorem 11. For a simple connected graph G with δ ≥ 2 and g(G) ≥ 7, γ_R(G)≥2∆. This bound is sharp forg(G) = 7.

Proof. Letf = (V₀^f, V₁^f, V₂^f) be a γ_R(G)-function such that|V₁^f|is minimum and let C be a cycle of G with g(G) edges. Suppose v ∈ V(G) is a vertex with degree ∆. By Theorem D,V₁^f is an independent set ofGandN(w1)∩N(w2) =∅ ifw16=w2forw1, w2∈V₁^f. ConsiderN(v) ={v1, v2, . . . , v∆}. Forv /∈V₂^f, similar to the proof of Theorem 9, the statement follows. Forv ∈V₂^f, let A=N[v]∩V₂^f andB=N(v)∩V₀^f. Foru∈B, three cases might occur.

Case 1. uhas a neighbor inV₂^f− {v}. In this case, considerxu∈(V₂^f− {v})∩ N(u).

Case 2. uhas no neighbor inV₂^f− {v}and uhas some neighbor in V₀^f. For yu∈N(u)∩V₀^f, Sinceg(G)≥7,yu6∈B. In this case, letxu∈V₂^f ∩N(yu).

Case 3. u has no neighbor in V₀^f ∪(V₂^f− {v}) and uhas some neighbor in V₁^f. For z_u ∈ V₁^f ∩N(u), Since Gis connected and δ ≥2, z_u has a neighbor in V₀^f− {u}, sayyu. On the other handyu has a neighbor inV₂^f, sayxu.

Sinceg(G)≥7, it is straightforward to verify thatA∩ {x_u |u∈B}=∅ and xu6=xu⁰ whenu6=u⁰ andu, u⁰∈B. Thus,|V₂^f| ≥∆ that implies the statement.

The bound is sharp for the graph G= (V, E), where V ={v, u, w, vi, ui, wi | 1 ≤i≤m} and E ={vu, uw, w1w2, vvi, viui, uiwi |1 ≤i≤m} for m≥2 when g(G) = 7.

REFERENCES

[1] A.P. Burger, E.J. Cockayne, W.R. Gr¨undlingh, C.M. Mynhardt, J.H. van Vuuren and W.

Winterbach. Finite order domination in graphs, J. Combin. Math. Combin. Comput.49 (2004), 159-175.

[2] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. (to appear).

[3] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi,On Roman domination in graphs, Discrete Math.278(2004), 11-22.

[4] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi and A.A. McRae, The algorithmic complexity of Roman domination, (submitted).

[5] E.J. Cockayne, O. Favaron, and C.M. Mynhardt,Secure domination, weak Roman domina- tion and forbidden subgraphs, Bull. Inst. Combin. Appl.39(2003), 87-100.

[6] E.J. Cockayne, P.J.P. Grobler, W.R. Gr¨undlingh, J. Munganga and J.H. van Vuuren, Pro- tection of a graph, Util. Math.67(2005), 1932.

[7] O. Favaron, H. Karami and S.M. Sheikholeslami,On the Roman domination number of a graph, Discrete Math. (2008), doi:10.1016/j.disc.2008.09.043.

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs, Marcel Dekker, Inc., New York, 1998.

[9] M.A. Henning,A characterization of Roman trees, Discuss. Math. Graph Theory22(2) (2002), 325–334.

[10] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math.271 (2003), 101-115.

[11] M.A. Henning and S.T. Hedetniemi,Defending the Roman Empire a new strategy, The 18th British Combinatorial Conference (Brighton, 2001). Discrete Math.266(2003), 239-251.

[12] M. Liedloff, T. Kloks, J. Liu and S.-L. Peng,Roman domination over some graph classes, Graph-theoretic concepts in computer science, 103-114, Lecture Notes in Comput. Sci., 3787, Springer, Berlin, 2005.

[13] C.S. Revelle and K.E. Rosing,Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly107(7) (2000), 585–594.

[14] X. Song and X. Wang,Roman domination number and domination number of a tree, Chinese Quart. J. Math.21(2006), 358-367.

[15] I. Stewart,Defend the Roman Empire, Sci. Amer.281(6) (1999), 136-139.

[16] H.-M. Xing, X. Chen and X.-G. Chen,A note on Roman domination in graphs, Discrete Math.306(2006), 3338-3340.

(received 04.12.2007, in revised form 12.07.2008)

S.M. Sheikholeslami, Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, I.R. Iran

E-mail:[email protected]