Total Roman Domination In Special Type Interval Graph

Download Full-Text PDF Cite this Publication

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.

Leave a Reply

Your email address will not be published. Required fields are marked *