Issuu

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

ON STRONG BLAST DOMINATION OF GRAPHS M. Lalitha kumari1, Dr.V. Anusuya2 1M.Phil Scholar, Department of Mathematics, S.T.Hindu college, Nagercoil, TamilNadu, India

2Dr.V.Anusuya, Assistant Professor, Department of Mathematics, S.T.Hindu college, Nagercoil, TamilNadu, India

---------------------------------------------------------------------***----------------------------------------------------------------------

Abstract - In this paper, we introduce another new domination parameter called, the strong blast domination of a graph with real life applications. A subset S of V of a non-trivial graph G is said to be strong blast dominating set if S is a connected dominating set and the induced sub graph is triple connected and also for each vertex v in V-S there exist some ( ) Strong Blast Domination Number is denoted by ( ) In this paper, we find the Strong vertex u in S such that ( ) Blast Domination Number for Complete graph, Wheel graph, Peterson graph, Total graph of friendship graph, Total graph of Path, Total graph of Cycle, Total graph of wheel, Quasi-total graph of Complete graph and Friendship graph. Key Words: Domination number, connected domination number, Triple connected, Strong domination, Total graph, Quasi-total graph. 1. INTRODUCTION Throughout this paper, we consider only finite simple undirected connected graph. The order and the size are denoted by n and m respectively. Degree of a vertex v is denoted by ( ), the maximum degree of a graph G is denoted by ( ) A path on vertices is denoted by A graph is complete if every pair of its vertices are adjacent. A complete graph on n vertices denoted by A cycle of length n is denoted by . The total graph T(G) of a graph G is defined with the vertex set ( ) ( ), in which two vertices are adjacent if and only if (i) Both are adjacent edges or vertices in G (or) (ii) One is a vertex and other is an edge incident to it in G. The Quasi-total graph P(G) of a graph is a graph whose vertex set is ( ) ( ) and two vertices are adjacent if and only if they correspond to two non adjacent vertices of or to two adjacent edges of or one is a vertex and other is an edge incident with it in . The friendship graph is an one-point union of n copies of cycle . A Wheel graph of order n is a graph that contains a cycle of order and for which every vertex in the cycle is connected to one other vertex. The Peterson graph is an undirected graph with 10 vertices and 15 edges. The Windmill graph ( ) is an undirected graph constructed for by taking copies of the complete graph with a vertex in common. The barbell graph is an undirected graph obtained by connecting two copies of a complete graph by a bridge. The Sunlet graph is obtained by attaching a pendent edge to all the vertex of the cycle . In our literature survey, we are able to find many authors have introduced various new parameters by imposing conditions on the dominating sets. In that sequence, the concept of connectedness plays an important role in any network. A subset S of V of a non-trivial graph G is called a dominating set of G if every vertex in V-S is adjacent to at least one vertex S. The domination number ( ) is the minimum cardinality of a dominating set. The concept of triple connected graphs was introduced by Paulraj Joseph et.al , - A graph G is said to be triple connected if any three vertices lie on a path. In , - the authors introduced the concept of complementary triple connected domination number of a graph. A subset S of V of a non-trivial graph G is said to be complementary triple connected dominating set, if S is a dominating set and the induced sub graph is triple connected. The minimum cardinality taken over all complementary triple connected ( ). dominating sets is called the complementary triple connected domination number of G and is denoted by In , -, the authors introduced Blast domination number of a graph with real life applications. A subset S of V of a non-trivial graph G is said to be Blast dominating set, if S is a connected dominating set and the induced sub graph is triple connected. The minimum cardinality taken over all Blast dominating sets is called the Blast domination number and is denoted by ( ). A dominating set S is said to be a strong dominating set if for every vertex v in V-S ( ) and is denoted by ( ). dominated by some vertex u of S such that ( ) Now, we introduce a new domination parameter called Strong Blast Domination number. A subset S of V of a nontrivial graph G is said to be strong blast dominating set, if S is a connected dominating set and the induced sub graph ( ) and SBDN is denoted by is triple connected and also for each there exist such that ( ) ( ).

Impact Factor value: 7.34

ISO 9001:2008 Certified Journal

Page 5484

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

2. RESULTS     

( ) For complete graph with , . ( ) For wheel graph ( ), . ( ) For Peterson graph . ( ) For the Windmill graph , ( ) For the n-barbell graph with , .

3. EXAMPLES 3.1 For the graph

3.2 For the graph

+ is the Strong blast dominating set and

(

)

4. MAIN RESULTS Theorem 4.1 Let

be a connected graph of order n,

. Then

( )

if and only if

Proof: (

)

| | Hence

( ) Suppose * +) . Then (

and let * + be a of . Suppose , then there exists * + * +, which is not a dominating set of , since ( ). Therefore

Conversely, suppose that , the complement ( ) .

. Then * + ( ) is a is triple connected. And for all

(

) such that .

of . Since we have with there exist such that ( )

and ( ).

Theorem 4.2 Let

be a connected graph of order at least

vertices with no isolated vertices. Then ⌈

⌉

( )

Page 5485

( )

( ).

Impact Factor value: 7.34

ISO 9001:2008 Certified Journal

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

Proof: Let be a connected graph and ( ) ⌈ vertices. Hence ⌉.

be the

of . Each vertex can dominate at most itself and ( ) other

( )

For the upper bound, let be a vertex of maximum degree ( ). Then dominates itself and each of its neighbors , - dominates themselves. Thus , - is a dominating set with cardinality ( ). Also vertices in ( ). ( ) ( ) Therefore Theorem 4.3 Let

and ( )

be any connected graph with

. Then

( )

Proof: Let be a connected graph with and ( ) . Let be a vertex of degree ( ) . Let * + be the vertices which are adjacent to and let be the vertex which is not adjacent to . Since is connected, is adjacent to some for some . Then * + is a minimum connected dominating set. And the induced sub graph consists of at least 3 vertices which are lie on a path. So that is triple connected. ( ) Also for all there exists a vertex such that ( ) ( ). Hence . Theorem 4.4 For any connected graph

and ( )

with

, the strong blast domination number is either 2 or 3.

Proof: ( )

Let *

be the connected graph with ( ) * + and

and

and ( ) +.

, then *

then *

be the vertex of maximum degree n-3. Suppose

are not adjacent in .

Since is connected, there are vertices respectively. If

. Let

+ is a

and

+ is a

and

( ) ( )

and

for some

(

) which are adjacent to

and

. .

If and are adjacent in . Then there is a vertex or or both. In this case * + or * + or * number is either 2 or 3.

for some , ( ) which is adjacent to either + is a of . Hence the strong blast domination

Theorem 4.5 , -

of a graph

is a minimal dominating set if and only if

there exist

for which

* +.

Proof: (

Let )

be a of . Then for every vertex , * + that is not dominated by . This implies that , -

Conversely let us presume that , there exist of . Then there is a vertex such that * + is a * +, also if * + is a dominating set then every vertex in contradiction to our assumption. Hence is a .

Impact Factor value: 7.34

* + is not a * +

. Thus there is a vertex

* + Suppose that is not a for which , of . Hence is adjacent to at least one vertex in is adjacent to at least one vertex in * +. This is a

ISO 9001:2008 Certified Journal

Page 5486

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

Theorem 4.6 If

is a graph with no isolated vertices and

is a

then

has a

Proof: Let be a from v to any vertex in has a dominating set.

of . Suppose has no dominating set of . Then for some vertex there is no edge . Then * + would be a dominating set, which contradict the minimality of . Hence

Result 4.7 For complete graph

the complement of a

is also a

Theorem 4.8 If

is a

1) 2)

has a ( )

Barbell graph with ( ).

, then

S such that every vertex in has at least three neighbors in

Proof: Let be a Barbell graph with joining the two complete graphs.

, obtained by joining two complete graphs by a bridge. Let

Let the vertices of the complete graphs be * Let ( ) * +. Since ( ) and ( ) , the vertices and ( ) dominating set of . Therefore, ( ) Clearly, the vertices

and

+ and *

+ be the edge

is adjacent to * + and is adjacent to * dominates all the vertices of the Barbell graph. Let ( ) .

are adjacent to at least three neighborhoods of

+, where + be the

. Hence ( ) follows.

Since * + is the bridge which connects the complete graphs, which is connected. Also since , the induced sub graph must has at least three vertices which are lie on a path. Therefore must be triple connected. And all the vertices strongly dominated by a vertex . Hence is a . Thus,

( )

. Hence, ( )

( ). This proves ( ).

Theorem 4.9 (

For any corona graph

)

where

Proof: Let ( set *

) * +. Let be the path having vertex set * +. Continuing like this we get be the path having vertex set *

be the path having vertex +. + Here

Therefore * + is a dominating set of . Also each vertex of has at least 3 neighbors in Thus induces a triple connected subgraph. Also, clearly all the vertices in has maximum degree as ( ) ( Thus for each vertex in there is a vertex in such that ( ) ( ). Hence is a . ie, | | .

. .

Vertex set of the corona adjacent to is adjacent to …and

is, * is adjacent to

+ and

)

Theorem 4.10 For the corona of

and

with

Impact Factor value: 7.34

ISO 9001:2008 Certified Journal

Page 5487

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

(

)

(

)

(

Let the vertices of

and

be *

www.irjet.net )

(

)

Proof:

(

)

(

)

+ and *

+ respectively. And for the corona

, ,

(

)

(

)

Comparing the above equations we get, (

)

(

)

(

)

(

Observation 4.11 For the corona of (

)

and

with

(

)

(

)

(

)

Theorem 4.12 [ (

)]

Proof: Let (

) be the total graph of the star graph having the vertex set

+ * [ ( )] ( ) ( )=* + * +, in which the vertices * + * + induces a clique of order and the vertex is adjacent to * +. Since * + dominates all the vertices of ( ) and is also connected, we get * + forms the minimum Blast dominating set of ( ). Since ( ) in ( ) and which is the maximum degree of a vertex in ( ), for every vertex [ ( )] * +, there is a vertex such that ( ) ( ) Hence is a Strong blast dominating set. Therefore, the Strong Blast Domination Number of the total graph of star graph is, [ ( )] Theorem 4.13 For any

graph

(

, ( )-

Proof: Let ( ) * + and let be the pendant vertex adjacent to , . Let be a vertex of ( ) , ( )corresponding to the edge in . Then * + is a of ( ). Thus . Further, any , ( )dominating set of ( ) must contains at least one of and hence | | . So that . Hence , ( ). Theorem 4.14 For any wheel

(

, (

⌊ ⌋

Proof: Let ( ) * + and , ( )- * * ++ where is the vertex of ( ) corresponding to the edge vertex of ( ) corresponding to the edge ( ). Suppose

+ of

(

+ ) and

(

) is the

is odd.

Impact Factor value: 7.34

ISO 9001:2008 Certified Journal

Page 5488

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

Let be the independent set of the cycle with respect to the wheel ⌊ ⌋. Then * + where v is the apex vertex of is the

| |

, (

⌊ ⌋

Suppose

+ and . Hence

⌊ ⌋

. is even.

As before let ⌊ ⌋ Then

| |

. Therefore * of ( ) and | |

* * + *

+ be the independent set of the cycle with respect to the wheel , ( )- ⌊ ⌋ + is the of ( ) and | | ⌊ ⌋ . Hence .

and

Theorem 4.15 , (

Let

be the vertices of

Proof: and

( ) be the edges of

vertex set of ( ). Therefore | , ( )-| ( ). Each edge ( with 2 vertices. Let be a vertex of ( ) corresponding to and Therefore dominates vertices including itself in ( ). Thus there are ( ) vertices in ) belongs to the set .

(

. Then *

( ) + is the

( )) is adjacent to ( . Then adjacent to (

) which are need to be dominated. Let such * ( ) +.

) edges and incident ) vertices of ( ). (

) and

Let be a vertex of ( ) corresponding to and So that dominates at least three vertices in . Choose adjacent to and which is also dominate at least 3 vertices of . Proceeding like this until all the vertices of ( ) dominated by minimum number of vertices. Thus we get as a minimum connected dominating set of cardinality . Also every vertex of has maximum degree ( ). Therefore , ( )Hence is a and .

is a

. And

is triple connected.

Theorem 4.16 , ( )-

Proof: Let *

+ be the vertex set of

The vertex set of ( ) is, *

and *

+ be the edge set of + and | , ( )-|

. .

We prove this result by induction on . Suppose Then has 3 vertices and 3 edges. Therefore ( ) has 6 vertices namely * +. Let be the apex vertex of . Let be a vertex of ( ) which is incident with in . Therefore dominates 5 vertices including itself. Since ( ) is connected, the remaining one vertex is adjacent to some ( ). Choose adjacent with so that dominates the remaining one vertex of ( ). *

+ is a minimum connected dominating set and there exist some vertices such that ( ) | | and for triple connected we need at least 3 vertices. So , ( ). Hence the result is true for . Let us assume that the result is true for , (

( ) ( ) ( ) . Thus for every vertex ( ). Therefore is a strong dominating set, also is triple connected. Thus is a and

. i.e. There exist a

(

Impact Factor value: 7.34

such that | |

(

ISO 9001:2008 Certified Journal

Page 5489

International Research Journal of Engineering and Technology (IRJET)

e-ISSN: 2395-0056

Volume: 07 Issue: 03 | Mar 2020

p-ISSN: 2395-0072

www.irjet.net

Now, we prove the result for . such that any one of the vertex of incident with the apex vertex of . For , ( )( ). Now for , * + * + * + where * + * + is the * + * + * +. |

| | (

, ( )-

, we have, of ( ). Let

)

. Thus the result is true for n. Hence the result is true for all .

3. CONCLUSION In this paper, we computed the exact values of strong blast domination for some total graph, quasi total graph, corona product of some graphs. Also we derive several general results on this domination parameter. REFERENCES [1] G. Mahadevan, A. Ahila and Selvam Avadayappan, Blast Domination Number of a Graph – Preprint [Communicated in Global Journal Of Pure and Applied Mathematics]. [2] G. Mahadevan, A. Selvam, J. Paulraj Joseph, B. Ayisha and T. Subramanian, Complementary triple connected domination number of a graph, Advances and Applications in Discrete Mathematics, Vol. 12 (I) (2013), 39 - 54. [3] G. Mahadevan, A. Selvam, J. Paulraj Joseph and T. Subramanian, Triple connected domination number of a graph, International Journal of Mathematical Combinatorics, Vol.3 (2012), 93 – 104. [4] Harary.F Graoh Theory, Addison Wesley Reading Mass(1972). [5] J. Paulraj Joseph, M. K. Angel Jebitha, P. Chithra Devi and G. Sudhana, Triple connected graphs, Indian Journal of Mathematics and Mathematical Sciences, Vol.8, No.I(2012),61–75. [6] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.

Impact Factor value: 7.34

ISO 9001:2008 Certified Journal

Page 5490