Total restrained reinforcement in graphs

Peer review under responsibility of Kalasalingam University.

Abstract

In this paper we initiate the study of total restrained reinforcement in graphs. The total restrained reinforcement number in a graph with no isolated vertex, is the minimum number of edges that have to be added to so that the resulting graph has total restrained domination number less than total restrained domination number of . We obtain sharp bounds, exact values and characterization for the total restrained reinforcement number of a graph.

Keywords:

• Domination
• Total restrained domination
• Reinforcement

1 Introduction

Let be a simple graph of order . We denote the open neighborhood of a vertex of by , or just , and its closed neighborhood by . For a vertex set , and . Let be a set of vertices, and let . We define the private neighbor set of , with respect to , to be . A set of vertices in is a dominating set, if . The domination number, of , is the minimum cardinality of a dominating set of . A set of vertices in is a total dominating set, if . The total domination number, of , is the minimum cardinality of a total dominating set of . A set is a total restrained dominating set, denoted TRDS, if every vertex is adjacent to a vertex in and every vertex in is also adjacent to a vertex in . The total restrained domination number of , denoted , is the minimum cardinality of a total restrained dominating set of . A TRDS of cardinality is called a -set. For references on domination in graphs see [1–^[2][3][4][5]6].

If is a subset of , then we denote by the subgraph of induced by . We recall that a leaf in a graph is a vertex of degree one, and a support vertex is one that is adjacent to a leaf. Let be the set of all support vertices in a graph .

Kok and Mynhardt [7] introduced the reinforcement number of a graph as the minimum number of edges that have to be added to so that the resulting graph satisfies . They also defined if . This idea was further considered for some other varieties of domination such as fractional domination, independent domination, and total domination, [8^[9]–^[10]11].

In this paper we study reinforcement by considering a variation based on total restrained domination. The total restrained reinforcement number of a graph with no isolated vertex, is the minimum number of edges that have to be added to so that the resulting graph satisfies . We also define if . We determine for some classes of graphs and obtain several upper bounds.

With we denote the complete graph on vertices, with the path on vertices, and with the cycle of length . For two positive integers , the complete bipartite graph is the graph with partition such that , and such that has no edge for , and every two vertices belonging to different partite sets are adjacent to each other. Obviously, for any two integers , we have , where is the wheel and is the fan of order .

2 Exact values

We begin with the following proposition.

Proposition 2.1

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

Proof

If , then trivially . Assume that . By adding to all edges belonging to , we obtain a complete graph . Since , we deduce that , and the result follows. □

In the following we obtain the total restrained reinforcement number for paths and cycles.

Observation 2.2

[1]

(1)

For ,

(2)

For ,

Proposition 2.3

Let be an integer. Then

Proof

The result is obvious for . Let now and . For (mod 4), by Observation 2.2, , giving that . For (mod 4), let . Then is a TRDS for , giving that . Thus we assume that (mod 4).

There is an integer such that . By Observation 2.2, . We show that . Suppose to the contrary that for some . By Observation 2.2, . Let , , and let be a -set. Without loss of generality, assume that . Then a component of has more than two vertices. In order for to dominate the maximum number of vertices, we may assume that a component of has three vertices, and any other component is a path on two vertices. If , then dominates at most 7 vertices of and any other component of dominates at most 4 vertices of . But clearly . Now dominates at most vertices of , a contradiction. Thus we assume that . If , then and by Observation 2.2, , a contradiction. Thus, without loss of generality, we may assume that and . Then dominates at most 6 vertices of and any other component of dominates at most 4 vertices of . But clearly . Thus dominates at most vertices of , a contradiction. Thus . On the other hand if is a -set, then is a TRDS for . Hence . □

Proposition 2.4

Let be an integer. Then

Proof

The result is obvious for . Let and . First let (mod 4). There is an integer such that . By Observation 2.2, . Let be an arbitrary edge of and . Let be a -set. We show that . Suppose to the contrary that . Without loss of generality assume that . Then a component of has more than two vertices. In order for to dominate the maximum number of vertices, we may assume that a component of has three vertices, and any other component is a path on two vertices. Assume that . Then dominates at most 5 vertices of . If , then dominates at most vertices of , a contradiction. Thus , and similarly . Now is a TRDS for , a contradiction. We deduce that . Without loss of generality, assume that . Assume that . If , then dominates at most vertices of , a contradiction. Thus . Then dominates at most 5 vertices of , and at the component dominates 6 vertices of . Thus dominates at most , a contradiction. We thus assume that . Then dominates at most vertices if is even and at most vertices if is odd. In each possibility dominates less than vertices, a contradiction. We deduce that . On the other hand is a TRDS for of cardinality less than . We conclude that .

Now let (mod 4). If (mod 4), then for some . Then is a TRDS for of cardinality less than . So . The proof for (mod 4) is similar and is therefore omitted. □

3 Upper bounds

Theorem 3.1

Let be a connected graph of order . If has at least two leaves, then .

Proof

Let and be two leaves of , and let be a -set.

Assume first that and have distance two. Let be the common neighbor of and . Since the order , there exists a further neighbor of . Clearly, contains the vertices and . If , then is a TRDS for . Thus assume that . Then is a TRDS for . This implies that .

Assume second that and have distance at least three. Let and be the neighbors of and , respectively. Since and have distance at least three, we see that . Clearly, contains the vertices and , while is a TRDS of . Thus , and the proof is complete. □

Proposition 2.3 shows that the bound in Theorem 3.1 is sharp.

Corollary 3.2

If is a tree of order , then .

The next result provides a characterization for a graph with .

Theorem 3.3

Let , where is a graph with no isolated vertex. Then if and only if for any -set the following hold:

(1)	If , then or .

(2)	If , then or .

(3)	If and , then .

Proof

Let , where is a graph with no isolated vertex. Assume that . Let be a -set. If , and , then is a TRDS for and so , a contradiction. So (1) holds. Similarly, (2) and (3) hold.

For the converse suppose to the contrary that . Let be a -set. It follows that is a TRDS for and thus is a -set. If , then and , contradicting (1). So . If , then and , contradicting (2). It remains to assume that and . This time we get a contradiction according to (3). We conclude that . □

Corollary 3.2 and Theorem 3.3 provide a characterization for trees with or 2.

Let be the class of all connected graphs such that if and only if every edge of is incident to a support vertex, or if is a cycle on three vertices.

Theorem 3.4

Cyman and Raczek, [2]

If is a connected graph of order , then if and only if .

Proposition 3.5

Let be a tree of order . If the diameter of is at most 4, then .

Proof

Since the diameter of is at most 4, we observe that every edge of is incident to a support vertex. According to Theorem 3.4, it follows that . If and are two leaves of , then is a TRDS for and so . Proposition 2.1 leads to and thus . □

Proposition 2.3 shows that Proposition 3.5 is not valid in general when the diameter of the tree is at least five.

We next give a sharp upper bound for the total restrained reinforcement number.

Theorem 3.6

If is a connected graph of order , then , and this bound is sharp. If , then is even and each component of every -set is a .

Proof

Let be a connected graph. If , then Proposition 2.1 implies that . Assume next that . Let be a -set.

Assume first that . By Proposition 2.4 and Theorem 3.4, we may assume that every edge of is incident to a support vertex. Let be two leaves of . Then is a TRDS for and so .

Assume next that .

First we assume that . Let be a longest path in . Then , since . As , there is an integer such that has neighbor in . If , then we join any private neighbor of in to to obtain a graph . It follows that is a TRDS for , implying that . Similarly if , then . Thus we assume that . Let . We add the edges , for all neighbors of in , and for all vertices , and then remove multiple edges, to obtain a graph . It is easy to see that and so .

Finally, we assume that and so each component of is a . Let and be two edges in such that . We join any vertex of to to obtain a graph . It is obvious that is a TRDS for , and so . The sharpness follows from Proposition 2.4, at least for .

If , then from the above argument, is even and each component of every -set is a . □

An efficient total restrained dominating set in is a TRDS such that and for two different vertices .

Theorem 3.7

For a graph , if and only if for any -set , the following hold:

(1)

.

(2)	Each vertex of is of maximum degree in .

(3)	is an efficient total restrained dominating set.

Proof

Let be a graph with .

() Let be a -set.

(1)	Follows from Theorem 3.6.

(2)	Let . Suppose that . Let be adjacent to . Since , . Let . We join every vertex of to to obtain a graph . Then is a TRDS for , and so . This contradiction implies that .

(3)

Suppose that is not an efficient TRDS. There are such that . First suppose that are not adjacent. Let be adjacent to , and be adjacent to . We join every vertex of to to obtain a graph . Then is a TRDS for , and so , a contradiction. If are adjacent, then we join every vertex of to for some to obtain a graph . Then is a TRDS for , and so , a contradiction.

() By our assumptions both and are even. Let be a minimum set of edges of such that . Then . Let and be a -set. Let be a subset of vertices of with such that has no isolated vertex and is maximum. Then . We show . Suppose to the contrary that . Then . Suppose that is odd. Then is odd and at least one component of has more than two vertices. Since is maximum, we may assume that a component of has three vertices, and any other component is a .

We know that a subset of vertices of cardinality totally dominate at most vertices of if is even, and at most vertices if is odd.

This is a contradiction. If is even then, without loss of generality, we may assume that any component of is a . This time, we similarly obtain , a contradiction.

So . On the other hand let be a -set, and . We join to and to any vertex of , to obtain a graph . It is now easy to see that is a TDS for of cardinality . We deduce that . This completes the proof. □

Theorem 3.8

If is a graph of order with , then

Proof

Let be a -set. If for each vertex , then , a contradiction. Thus there is a vertex such that . Let , and let . We join to every vertex of to obtain a graph .

Assume first that . Then is a TRDS for and so .

Assume next that and . Since , there exists a vertex . In we join to to obtain a graph . Now is a TRDS for and so .

Now assume that and with . In we join to to obtain a graph . Now is a TRDS for and hence .

Finally, assume that . Let . If is even, then we join in the vertices to for to obtain the graph . The set is a TRDS for and therefore

If is odd, then we join in the vertices to for and to to obtain the graph . The set is a TRDS for and thus Therefore the first inequality is proved. Using the first inequality and the fact that , we obtain This leads to the second inequality, and the proof is complete. □

Problem 3.9

Find a constructive characterization of trees with and .

Notes

Peer review under responsibility of Kalasalingam University.