# Total Roman Domination In Special Type Interval Graph

Text Only Version

#### Total Roman Domination In Special Type Interval Graph

M. Reddappa

Dept. of Mathematics, S.V.University, Research Scholar,

Tirupati-517502, India..

Dr. C. Jaya Subba Reddy

Dept. of Mathematics, S. V. University, Assistant Professor,

Tirupati-517502, India..

Abstract Interval graphs have drawn the attention of many researchers for over 40 years. They form a special class of graphs with many interesting properties and revealed their practical relevance for modeling problems arising in the real world. The theory of domination in graphs introduced by O. Ore [10] and C. Berge [1] has been ever green of graph theory

A Roman dominating function on a graph is a function satisfying the condition that every vertex for which is adjacent to at least

one vertex for which The weight of a Roman

today. An introduction and an extensive overview on domination in graphs and related topics is surveyed and detailed in the two

dominating function is the value

f (v) . The

vV

books by T. W. Haynes et.al. [12, 13].

Keywords Total domination number, Total Roman dominating function, Total Roman domination number, Interval family, Interval graph.

1. INTRODUCTION

Domination in graphs has been studied extensively in recent years and it is an important branch of Graph Theory. R.B.Allan and R.C. Laskar [11], E.J. Cockayne and S.T. Hedetniemi, [4] and many others have studied various domination parameters of graphs.

Let be a graph. A total dominating set of a graph G with no isolated vertices is a set S of vertices of G such that every vertex in V(G) is adjacent to at least one vertex in S.

The minimum cardinality of a total dominating set is called as total domination number and it is denoted by . A total dominating set of G of cardinality is called a .-set.

Total domination in graphs was introduced by E. J. Cokayne et al. [6]. Total domination is now well studied in graph theory. The literature on the subject of total domination in graphs has been surveyed and detailed in the recent book by M.A. Henning et al. [9].

We consider finite graphs without loops and multiple edges.

minimum weight of a Roman dominating function on a graph is called as the Roman domination number of . It is denoted by . If = 2 then G is called a Roman graph.

Let and let be the ordered partition of induced by f where

for Then there

exists a 1-1 correspondence between the functions

and the ordered partition of

. Thus we write .

A function becomes a Roman dominating function if the set dominates .

Total Roman domination in graphs are studied by

Ahangar et al. [7]. A total Roman dominating function of a graph G with no isolated vertices, is a Roman dominating function f on G with the additional property that the sub graph of G induced by the set of all vertices of positive weight under f has no isolated vertices.

The minimum weight of a total Roman dominating function is called as the total Roman domination number of G and it is denoted by . A total Roman dominating function with minimum weight is called – function. If then G is called a total Roman graph.

1. TOTAL ROMAN DOMINATING FUNCTION

The Roman dominating function of a graph was defined by E. J. Cockayne et.al. [5]. The definition of a Roman dominating function was motivated by an article in Scientific American by Ian Stewart [8] entitled Defend The Roman Empire! and suggested even earlier by C.

S. ReVelle [3]. Domination number and Roman domination number in an interval graph with consecutive cliques of size 3 are studied by C. Jaya Subba Reddy, M. Reddappa and B. Maheswari [2].

2. INTERVAL GRAPH

Let be an interval

family, where each is an interval on the real line and = ] for Here is called the left end point and is called the right end point of . Without loss of generality, we assume that all end points of the intervals in are distinct numbers between 1 and 2n. Two intervals i = ] and j = [ ] are said to

intersect each other if either or . The

intervals are labelled in the increasing order of their right end points.

Let be a graph. G is called an interval graph if there is a 1-1 correspondence between and such that two vertices of are joined by an edge in if and only if their corresponding intervals in intersect. If is an interval in the corresponding vertex in is denoted by .

Consider the following interval family.

I3 I6

I1

I4

I2 I5

The corresponding interval graph is

v1

v2

v6

v3

, are total

dominating sets of respectively. Further we can show that all these sets are minimum total dominating sets. Therefore the total domination numbers of are for

and for

If k =2, then

For and for

, and for

and for

are minimum total dominating sets of . So the total domination numbers are for and

for respectively.

Similarly for k =3 we have

Then the minimum total dominating sets are

for

;

for

;

for

;

for

.

Hence for and for

v5

Thus for

v4 for

for

In what follows we consider interval graphs of this type. That is the interval graph which has consecutive cliques of size 3. We denote this type of interval graph by . The total domination and total Roman domination number is studied in the following for the interval graph .

3. RESULTS

Theorem 4.1: Let be the Interval graph with n vertices and no isolated vertices, where n . Then the total domination number of is

for n

for

for

for .

Hence we get that the general form of total dominating sets of

as

for for

where respectively.

Proof: Let be the Interval graph with vertex set

and no isolated

for

for

for for

vertices, where n .

Suppose k =1. Then We can easily see that is a total dominating set of .

Now for we see that

and for and for

for for

and so on.

Thus for n

g(v) g(v) g(v) g(v)

for

vV '

vV0

vV1

vV2

where respectively.

Theorem 4.2: Let be the interval graph with n vertices and no isolated vertices, where . Then

Proof: Let be the interval graph with n vertices and no isolated vertices, where . Let

{ } be the vertices of .

Then it is clear that is the total dominating set when

n = 3, 4 and is the total dominating set when

and is the total dominating set for

.

That is

Theorem 4.3: Let be the interval graph with n vertices and no isolated vertices, where n . Then the total Roman domination number of is

for

= for

.

where respectively.

Proof: Let be the interval graph with n vertices and no isolated vertices, where n .

Since is a minimum total dominating set of , we have

. Further , since . This implies that

.Thus

is the minimum weight of , where is a total Roman dominating function.

Therefore

Case 2: Suppose , where .

Now we proceed as in Case 1.

Let ,

;

.

Clearly is a minimum total dominating set of . Here we observe that the set dominates .

Therefore becomes a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

Let the vertex set of

vV vV

vV vV

be .

Case 1: Suppose , where .

Let and let be the ordered partition of induced by f where

for Then there exist a -1 correspondence between the functions

and the ordered pairs of

.Thus we write .

Let ;

;

0 1 2

= = 4 +2.

Let be a total Roman

dominating function of . Then we can show as in Case 1, that is a minimum weight of for the total Roman dominating function .

Thus

Case 3: Suppose , where . Now we proceed as in Case 1.

Let ;

=V-{ }

. ;

By Theorem 4.1, we see that is a minimum total dominating set of . Further the set dominates . In addition the induced sub graph on is a sub graph of

with no isolated vertices.

Therefore is a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

.

Obviously is a minimum total dominating set of . Here we observe that the set dominates .

Therefore becomes a total Roman dominating function of .

Now

vV vV0

vV1

vV2

Therefore f (v) f (v) f (v) f (v) .

= = 4 +2

vV vV0

vV1

vV2

Let be a total Roman dominating function of , where dominates . Then

= = 4 +4.

Let be a total Roman

dominating function of . Then similar lines to Case 1, we

can show that is a minimum weight of for the total Roman dominating function .

Thus

Case 4: Suppose , where . Now we proceed as in Case 1.

Let ;

;

.

Again is a minimum total dominating set of . Further the

.

Here is a minimum total dominating set of and we observe that the set dominates .

Therefore becomes a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

set dominates .

vV vV0

vV1

vV2

Therefore becomes a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

= = 4 +4.

Let be a total Roman

dominating function of . Then we can show as in Case 1, that is a minimum weight of for the total Roman dominating function .

vV vV0

vV1

vV2

Thus

= = 4 +4.

Let be a total Roman

dominating function of . In similar lines to Case 1, we can show that is a minimum weight of for the total Roman dominating function .

Thus

Case 5: Suppose ,where . Now we proceed as in Case 1.

Let ;

;

.

Clearly is a minimum total dominating set of . Here we

Case 7: Suppose , where .

Now we proceed as in Case 1.

Let ,

.

We have seen that is a minimum total dominating set of and we observe that the set dominates .

Therefore becomes a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

observe that the set dominates .

vV vV0

vV1

vV2

Therefore becomes a total Roman dominating function of .

Now

Therefore f (v) f (v) f (v) f (v) .

= = 4 +4.

Let be a total Roman

dominating function of . In similar lines to Case 1, we can show that is a minimum weight of for the total Roman dominating function .

vV vV0

vV1

vV2

Thus

= = 4 +4.

Let be a total Roman

dominating function of . Then we can show as in Case 1, that is a minimum weight of for the total Roman dominating function .

Thus

Case 6: Suppose , where . Now we proceed as in Case 1.

Let ;

Theorem 4.4: Let be the interval graph with n vertices and no isolated vertices, where . Then the total Roman domination number is

for

= 4 for

Proof: Let be the interval graph with n vertices and no isolated vertices, where . Let

{ } be the vertices of .

Case 1: Suppose . Let be the vertices of

.

Let ;

; .

Obviously is a minimum total dominating set of and the set dominates .

Therefore is a total Roman dominating function of .

Therefore f (v) f (v) f (v) f (v) .

Proof : Let be the interval graph with n vertices and no isolated vertices, where .

Then it is clear that when we have seen by Theorem 4.4 and Theorem 4.2 that

Thus

Theorem 4.6: Let be the interval graph with n = 7 vertices and no isolated vertices. If . Then

is a total Roman graph.

vV vV0

vV1

vV2

Proof: Let be the interval graph with n = 7 vertices and

= 0 + 1 2×1 = 3.

Suppose n = 7.

no isolated vertices.

Thus .

Case 2: Suppose . Let be the vertices of .

Let ; ;

.

Here is a minimum total dominating set of and the set dominates . In similar lines to Case 1, we

get .

Case 3: Suppose . Let be the

vertices of .

Let ; ;

.

Again is a minimum total dominating set of and the set dominates . In similar lines to Case

1, we get .

Case 4: Suppose Let , be the

vertices of .

Let ; ;

.

Here is a minimum total dominating set of and the set

dominates .

Therefore is a total Roman dominating function of .

Therefore f (v) f (v) f (v) f (v) .

Then we have and . Thus .

Hence is a total Roman graph.

Theorem 4.7: Let be the interval graph with n vertices and no isolated vertices, where n . Then is a total Roman graph, for ,

, where

respectively.

Proof: Let be the interval graph with n vertices and no isolated vertices, where n .

Case 1: Suppose

respectively.

Then by Theorem 4.3, we have the total Roman domination number as

= 2 .

Thus is a total Roman graph.

Case 2: Suppose

, where

respectively.

Then by Theorem 4.3, we have the total Roman domination number as

= 2 .

Therefore is a total Roman graph.

vV vV0

Thus

vV1

= 0 2×2 = 4

vV2

Theorem 4.8: Let be the interval graph with n vertices and no isolated vertices, where n . Then is a total Roman graph if and only if there exist a function

Case 5: Suppose Let be

the vertices of .

Let ; ;

.

Again is a minimum total dominating set of and the set dominates . In similar lines to Case 4, we get

.

Theorem 4.5: Let be the interval graph with n vertices and no isolated vertices, where . Then

with .

Proof: Let be the interval graph with n vertices and no isolated vertices, where n . Suppose is a total Roman graph. Let be a function of .

Then we know that dominates and

dominates V. In addition the induced sub graph is a sub graph of with no isolated vertices.

Hence =

= . But is a total Roman graph. So

= 2 . Then it follows that , which

establishes Theorem 4.3. v9

Conversely, suppose there is a function 2

of such that . By the v8

definition of function, we have dominates V

and since , it follows that dominates V. In addition the induced sub graph is a sub graph of

with no isolated vertices. As is a minimum total v7

dominating set, we have = . By the definition of 2

function we have = = 0

= 2 . v6

v10

0

0 v1

0

v2

Hence is a total Roman graph, which also establishes Theorem 4.3.

4. ILLUSTRATIONS

Illustration 1: n = 6

0

v5 2

v3 2

v4 0

I3 I6

I1 I4

I2 I5

f (v)

vV

and

; ; = V-{ }

Therefore .

V1

0 v2

V6 0

0

v3

2

v5

2 v4 0

and

REFERENCES

1. C. Berge, Graphs and Hyperactive graphs, North Holland, Amsterdam in graphs, Networks, vol.10, 1980, pp.211 215.

2. C. Jaya Subba Reddy, M. Reddappa and B.Maheswari, Roman domination in a certain type of interval graph, International Journal of Research and analytical Reviews, vol.6, Issue 1, 2019, pp. 665 672.

3. C.S. ReValle, and K,E. Rosing, Defendens imperium romanum: a classical problem in military Strategy, Amer. Math. Monthly, vol.107 (7), 2000, pp.585 -594.

4. E.J. Cockayne, and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7, 1977, pp. 247 -261.

5. E.J. Cockayne, P.A.,Dreyer, S.M.Hedetniemi, and S.T.Hedetniemi, Roman domination in graphs, Discrete math., vol.278, 2004, pp.11 -22

6. E. J. Cockayne., R.M. Dawes., S.T. Hedetniemi,Total domination in graphs, Networks, vol.10, 1980, pp.211-219.

7. Hossein Abdollahzadeh Ahangar, A. Michal Henning, Vladimir Samodivkin, Ismael G Yero, Total Roman domination in graphs,

f (v)

vV

; ; =V-{ }

.

Appl. Anal. Discrete math. vol.10, 2016, pp.501-517.

8. Ian Stewart Defend the Roman Empire!., Scientific American, vol.281(6), 1999, pp.136 -139.

9. M.A. Henning, A. Yeo Total domination in graphs,(Springer Mono graphs in Mathematics) ISBN:978-1-4614-6524-9 (Print) 978-1-4614-6525-6(Online), 2013.

Therefore .

Illustration 2: n = 10

I3 I6

10. O. Ore Theory of Graphs, Amer, Math.Soc. Collaq.Publ.38, Providence (1962).

11. R.B. Allan, and R.C. Laskar, On domination, Independent domination numbers of a Graph, Discrete Math., 23, 1978,

I9 pp. 73-76.

12. T.W. Haynes, , S.T. Hedetniemi, and P.J. Slater, Domination in

I1 I4

I2 I5

I7 I10

I8

graphs: Advanced Topics, Marcel Dekkar, Inc., New York, 1998.

13. T.W. Haynes, , S.T. Hedetniemi, and P.J.Slater, Fundamentals of domination in graphs, Marcel Dekkar, Inc., New York, 1998.