Maximal 2-rainbow domination number of a graph

Peer review under responsibility of Kalasalingam University.

Abstract

A 2-rainbow dominating function (2RDF) of a graph is a function from the vertex set to the set of all subsets of the set such that for any vertex with the condition is fulfilled, where is the open neighborhood of . A maximal 2-rainbow dominating function on a graph is a 2-rainbow dominating function such that the set is not a dominating set of . The weight of a maximal 2RDF is the value . The maximal 2-rainbow domination number of a graph , denoted by , is the minimum weight of a maximal 2RDF of . In this paper we initiate the study of maximal 2-rainbow domination number in graphs. We first show that the decision problem is NP-complete even when restricted to bipartite or chordal graphs, and then, we present some sharp bounds for . In addition, we determine the maximal rainbow domination number of some graphs.

Keywords:

• Maximal domination
• Rainbow domination
• Maximal rainbow domination

1 Introduction

For terminology and notation on graph theory not given here, the reader is referred to [1–31^[2]3]. In this paper, is a simple graph with vertex set and edge set . The order of is denoted by . For every vertex , the open neighborhood is the set and the closed neighborhood of is the set . The degree of a vertex is . The minimum and maximum degree of a graph are denoted by and , respectively. A graph is -regular if for each vertex of . The open neighborhood of a set is the set , and the closed neighborhood of is the set . A tree is an acyclic connected graph. The complement of a graph is denoted by . We write for the complete graph of order , for a path of order and for a cycle of length .

A subset of vertices of is a dominating set if . The domination number is the minimum cardinality of a dominating set of . A dominating set is said to be a maximal dominating set (MDS) if is not a dominating set of . The maximal domination number is the minimum cardinality of a maximal dominating set of . The definition of the maximal domination was given by Kulli and Janakiram [4]. For more information on maximal domination we refer the reader to [5,6].

A Roman dominating function (RDF) on a graph is defined in [7,8] as a function satisfying the condition that every vertex for which is adjacent to at least one vertex for which . The weight of an RDF is the value . A Roman dominating function can be represented by the ordered partition (or to refer ) of , where . In this representation, its weight is . A maximal Roman dominating function (MRDF) on a graph is a Roman dominating function such that is not a dominating set of . The maximal Roman domination number of a graph , denoted by , equals the minimum weight of an MRDF on . A -function is a maximal Roman dominating function of with weight . The maximal Roman domination was introduced by Ahangar et al. in [9] and has been studied in [10].

For a positive integer , a -rainbow dominating function (kRDF) of a graph is a function from the vertex set to the set of all subsets of the set such that for any vertex with the condition is fulfilled. The weight of a kRDF is the value . The -rainbow domination number of a graph , denoted by , is the minimum weight of a kRDF of . A -function is a -rainbow dominating function of with weight . Note that is the classical domination number . The -rainbow domination number was introduced by Brešar, Henning, and Rall [11] and has been studied by several authors [12–^{[13][14][15][16][17][18][19]}20].

A 2-rainbow dominating function can be represented by the ordered partition (or to refer ) of , where , , , . In this representation, its weight is .

A maximal 2-rainbow dominating function (M2RDF) on a graph is a 2-rainbow dominating function such that is not a dominating set of . The maximal 2-rainbow domination number of a graph , denoted by , equals the minimum weight of an M2RDF on . A -function is a maximal 2-rainbow dominating function of with weight . As is a maximal 2-rainbow dominating function of and since every maximal 2-rainbow dominating function is a 2-rainbow dominating function, we have (1) Since is a maximal dominating set when is an M2RDF, and since assigning to the vertices of a maximal dominating set yields an M2RDF, we observe that (2)

We note that maximal 2-rainbow domination number differs significantly from 2-rainbow domination number. For example, for , and .

Our purpose in this paper is to initiate the study of maximal 2-rainbow domination number in graphs. We first show that the decision problem is NP-complete even when restricted to bipartite or chordal graphs, and then we study basic properties and bounds for the maximal 2-rainbow domination number of a graph. In addition, we determine the maximal 2-rainbow domination number of some classes of graphs.

We make use of the following results in this paper.

Proposition A

[12]

For , .

Proposition B

[12]

For , .

Proposition C

[9]

Let be a connected graph of order . Then if and only if or where is a nonempty matching.

Proposition D

[9]

Let be a connected graph of order . Then if and only if or , where is a matching of .

Observation 1

For , .

Proof

Obviously, . Let be a -function. As every vertex of dominates all vertices, we must have and hence . By (1(1) ) we have .  ■

Observation 2

For and any non-empty matching of , .

Proof

Let . It follows from (2(2) ) and Proposition C that . Let and let . Then the function is obviously a maximal rainbow dominating function of of weight and hence . This completes the proof.  ■

2 Complexity of maximal 2-rainbow domination problem

In this section we consider the following decision problem regarding the maximal 2-rainbow domination number of a graph.

MAXIMAL 2-RAINBOW DOMINATION PROBLEM (M2RD-PROBLEM):

INSTANCE: A graph and a positive integer .

QUESTION: Is ?

To prove that the decision problem for maximal 2-rainbow domination is NP-complete, we use a polynomial time reduction from 2-rainbow domination problem.

2-RAINBOW DOMINATION PROBLEM (2RD-PROBLEM):

INSTANCE: A graph and a positive integer .

QUESTION: Is ?

As shown in [12], the 2-rainbow domination problem remains NP-complete even when restricted to bipartite or chordal graphs.

In order to present our results we need to introduce some additional terminology and notation. Given a graph of order and a graph with root vertex , the rooted product graph is defined as the graph obtained from and by taking one copy of and copies of and identifying the vertex of with the vertex in the th copy of for every [21]. More formally, assuming that and that the root vertex of is , we define the rooted product graph , where and Fig. 1 shows an example of the rooted product of graphs.

Fig. 1 Rooted product , where has degree two in .

Theorem 3

M2RD-PROBLEM problem is NP-complete, even when restricted to bipartite or chordal graphs.

Proof

Let be a graph of order . M2RD-PROBLEM is a member of NP, since for a given function of such that , we can check in polynomial time that is a 2-rainbow dominating function of and that does not dominate .

Now, we consider a rooted product graph , where is a graph of order with vertex set and is a graph with root constructed as follows. We begin with a cycle with set of vertices and set of edges . To obtain the graph , we add three vertices , and edges and . Notice that can be done in polynomial time.

Let be a -function and consider the function on such that:

•

for ;

•

for ;

•

for ;

•

and for ;

•

for .

Clearly is a maximal 2-rainbow dominating function of , since is not dominated by . Thus .

On the other hand, let be a -function. From the structure of , for any we deduce that either or we have three vertices , , and to which does not assign . Thus, Moreover, for all the vertex has to be 2-rainbowly dominated. So, it follows that

Thus . According to the structure of , once more, it is straightforward to observe that every 2-rainbow dominated function of , such that , has the following form.

•

for ;

•

for ;

•

for ;

•	for , where is any -function.

Hence, is a dominating set of , and, as a consequence, . So, the equality is obtained.

If is a bipartite, then is a bipartite. If is a chordal graph, then we construct a graph , where and . Clearly is chordal. By an analogous procedure, the equality is derived. Therefore, for , we infer that if and only if , which completes the reduction of the M2RD-PROBLEM from the 2RD-PROBLEM.  ■

3 Basic properties and bounds

In this section we study properties of maximal 2-rainbow domination and present some sharp bounds.

Proposition 4

For any nonempty graph of order , with equality if and only if and or and or there are two vertices such that has a subset of size which is not a dominating set of .

Proof

By (1(1) ), . If and is a -function, then clearly either , and or , and . It is easy to see that in each case, is a dominating set of , a contradiction. Hence .

If and , then let be a vertex of degree and suppose that is an isolated vertex. Clearly, the function is an M2RDF of and hence . If and then as above, we have . Suppose now that there are two vertices such that has a subset of size which is not a dominating set of . If is not dominated by , then obviously is an M2RDF of and hence .

Conversely, let . Assume that is a -function. Then, we may assume, without loss of generality, that or and . First let . Let and . Since must dominate all vertices in , we have . Since is an M2RDF of , has no neighbor in , otherwise dominates which is a contradiction. If , then and , and if , then and . Now let and . Let and . Clearly, each vertex in is adjacent to . Since is an M2RDF of , we may assume has no neighbor in . It follows that each vertex in is adjacent to . Thus, is a subset of of size which does not dominate . This completes the proof.  ■

Proposition 5

For any graph without isolated vertex,Furthermore, this bound is sharp.

Proof

Let be a -function and let be a vertex of minimum degree. Then either or . If , then has a neighbor in or has a neighbor in and a neighbor in . It is clear that is a maximal 2-rainbow dominating function on and hence . If , then the function is a maximal 2-rainbow dominating function on and hence .

To prove the sharpness, let be the graph obtained from by adding a new vertex and joining it to exactly one vertex of . Then and and the proof is complete.  ■

Corollary 6

For any tree of order , .

Next we present an upper bound for maximal 2-rainbow domination number of a graph in terms of its order and minimum degree.

Proposition 7

Let be a connected graph of order with . Then

Proof

Consider a diametral path in . Then, the function is an M2RDF of and hence . Thus and the proof is complete.  ■

Proposition 8

For any graph ,Furthermore, this bound is sharp.

Proof

Let be a -set. Since is an MDS, there is a vertex not dominated by . Define by for and otherwise. It is easy to see that is an M2RDF of and hence .

To prove the sharpness, let be the graph obtained from the complete by adding a new vertex and joining it to exactly one vertex of .  ■

In (1(1) ) we observe that . In the rest of this section we characterize all extremal graphs.

Lemma 9

For a graph , .

Proof

If is a -function, then obviously is a M2RDF of and hence .

To prove the lower bound, let be a -function and let for . We may assume that . Then . Define by if , when and if . Obviously, is a maximal Roman dominating function on with and the result follows.  ■

Theorem 10

Let be a connected graph of order . Then if and only if or .

Proof

If or , then clearly . Let . Then by Lemma 9. It follows from Proposition D that or , where is a matching of . Since for or where is a nonempty matching of , we deduce that or and the proof is complete.  ■

Theorem 11

Let be a connected graph of order at least 3. Then if and only if has a non-cut vertex such that

(a)

,

(b)	has a -function such that assigns 1 to all neighbors of in .

Proof

If (a) and (b) hold, then we can extend -function to a 2RDF of by defining . Clearly, is an M2RDF of and so . Thus .

Conversely, let . Assume is a -function such that is maximum. Let be the set of vertices which are not dominated by . Since dominates , we have . If , then the function is a -function such that is maximum and all vertices not dominated by belong to . Thus we may assume, without loss of generality, that . If some vertex , has a neighbor in or has a neighbor in and a neighbor in , then is a 2RDF of of weight less than which is a contradiction. Hence, and or for each .

Claim 1. is a complete graph.

Assume to the contrary that for some . Since is connected and or , we may assume that has a neighbor in . Then is a -function which contradicts the choice of .

Claim 2..

Let . If then for each , the function is a 2RDF of of weight less than which is a contradiction. Suppose and . Since is connected of order at least 3, we may assume . Since , the function is a 2RDF of of weight less than , a contradiction again.

Let . We may assume . We claim that is not a cut vertex. Suppose to the contrary that is a cut vertex and are the components of . Obviously, if a 2RDF of for each . Define by , if , if and otherwise. It is easy to see that is a 2RDF of of weight less than , a contradiction.

Thus is a non-cut vertex. Obviously, the function , restricted to , is a 2RDF of of weight which assigns 1 to all neighbors of in . Hence . It remains to prove that . Suppose to the contrary that and let be a -function. Then we can extend to a 2RDF of by defining implying that which is a contradiction. This completes the proof.  ■

4 Special values of maximal 2-rainbow domination numbers

In this section we determine the exact value of maximal 2-rainbow domination number of some classes of graphs including paths, cycles and complete multipartite graphs.

Proposition 12

For , and for .

Proof

Let and be the bipartite sets of . First let . It is easy to see that the function defined by and otherwise, is an M2RDF of weight 3 and hence by Proposition 4.

If , then clearly the function defined by and otherwise, is an M2RDF of of weight 3 and it follows from Proposition 4 that .

Finally, let . First note that the function defined by and otherwise, is an M2RDF of of weight and hence . Now let be a -function. If and , then clearly is a dominating set of , a contradiction. Let . If , then which is a contradiction. Hence that implies assigns 1 and 2 to some vertices in . If , then is a dominating set, a contradiction. Thus implying that . Similarly, if , then . In each case, and hence . This completes the proof.  ■

Proposition 13

Let be the complete -partite graph with and . Then .

Proof

Suppose are the partite sets of the complete -partite graph with , and let . It is easy to see that the function defined by , and otherwise, is an M2RDF of and so .

Now let be a -function. If and for some , then is a dominating set of which is a contradiction. As in the proof of Proposition 12, one can verify that and hence .  ■

Proposition 14

For , if is even and if is odd.

Proof

First let is even. Then the function defined by , for , for and otherwise, is an M2RDF of of weight and hence . Since , we deduce from Proposition A that .

Now let be odd. Then the functions and defined by and are the unique -functions. Obviously, and are not M2RDF on . Thus . On the other hand, the function defined by , , and otherwise, is an M2RDF of weight and hence . Thus for odd and the proof is complete.  ■

Proposition 15

For , if and if .

Proof

Let be a cycle on vertices. If , then the function defined by , is obviously an M2RDF of of weight implying that .

Now let . It is easy to see that for each . It follows from Theorem 11 and (1(1) ) that .

If , then define by for , for and otherwise. Obviously, is an M2RDF of of weight which implies that .

If , then define by for , for and otherwise. Clearly, is an M2RDF of of weight which implies that .

Let . Define by for , for and otherwise. It is easy to see that is an M2RDF of of weight and so .  ■

Notes

Peer review under responsibility of Kalasalingam University.