Total Roman Domination In Special Type Interval Graph

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.