ISSN (0970-2083)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

# SOME CHARACTERIZATION OF COMPLEMENTARY TRIPLE CONNECTED DOMINATION NUMBER OF 3 ÃÂ¢Ãâ¬Ãâ REGULAR GRAPHS

Mahadevan G1*, Iravithul Basira A2 and Sivagnanam C3

1Department of Mathematics, Gandhigram Rural Institute, Deemed University, Gandhigram, Dindigul, India

2Full Time Research Scholar, Department of Mathematics, Gandhigram Rural Institute - Deemed University, Gandhigram, Dindigul, India

3Department of General Requirements, College of Applied Science, Sur Sultanate of Oman

*Corresponding Author:
E-mail: drgmaha2014@gmail.com; j.basiraabbas@gmail.com; choshi71@gmail.com

Received Date: 07 August, 2017; Accepted Date: 20 December, 2017

Visit for more related articles at Journal of Industrial Pollution Control

## Abstract

A graph is said to be triple connected if any three vertices lie on a path in G. A subset S of V of a nontrivial graph G is said to be complementary triple connected dominating set, if S is a dominating set and the induced sub graph <V-S> 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 ϒctc (G). The minimum number of colours required to colour all the vertices such that adjacent vertices do not receive the same colour is called chromatic number χ(G). In this paper, we investigate 3 - regular graphs for which ϒctc (G)= X(G)=3.

#### Keywords

Domination number, Complementary triple connected domination number, Chromatic number

#### Introduction

The concept of triple connected graphs was introduced by (Paulraj, et al., 2012). A graph is said to be triple connected if any three vertices lie on a path in G. In (Paulraj, et al., 2012) the authors introduced triple connected domination number of a graph. A subset S of V of a nontrivial graph G is said to be triple connected dominating set is S is a dominating set and <S> is a triple connected. The minimum cardinality taken over all triple connected dominating sets is called the triple connected domination number of G and is denoted by γtc (G).

The concept of complementary triple connected graphs was introduced by (Harary, 1972; Haynes, et al., 1998; Mahadevan, et al., 2013). A subset S of V of a nontrivial graph G is said to be complementary triple connected dominating set, if S is a dominating set and the induced sub graph <V-S> 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 (G) .

The minimum number of colours required to colour all the vertices such that adjacent vertices do not receive the same colour is called chromatic number χ (G). Motivated by the above concept we investigate 3 - regular graphs whose complementary triple connected domination number equals chromatic number equals three. We use the following results.

#### Main Results

Observation

For any connected graph

Let G = (V,E) be a connected 3 - regular graph of order p with and. We consider 3 - regular graph for which. which gives, p ≤ 12. Since ( ) 3 G = , 6 ≤ p ≤ 12 and since G is 3 - regular, p must be even. Hence p = 6 or 8 or 10 or 12

Theorem

There does not exist a connected 3 - regular graph on 6 vertices, whose chromatic number equal to complementary triple connected domination number equals 3 (Mahadevan, et al., 2013).

Proof

Let V-S = {x,y,z}. Since <V—S> is triple connected, ÃÂ¢ÃÅ¸ÃÂ¨SÃÂ¢ÃÅ¸ÃÂ© ≠ K3 ,K2UK1. Hence <V—S> = K3 or P3. Let <V— S> = K3 or P3. Then the possible case of <S> = K3, P3. In all the above cases it is not possible to form 3 - regular graph, which is a contradiction. Hence no new graph exists.

Theorem

Let G be a connected 3 - regular graph on 8 vertices. Then (G) = (G) = 3 ctc χ γ , if and only if G is isomorphic to J1 (Fig. 1)

Proof

Let G be a connected 3 - regular graph on 8 vertices with . Since , there exists a ctc- set with 3 elements. Let S = {x,y,z} be such a set. Let V—S = { v1, v2, v3, v4, v5}. <S> = K3 or or K1UK2 or P3 and, , K5, W5, F2,, K5-{e},, , C3(P3), C3(2P2), C3(P2,P2,0) and the following (Fig. 2).

Since G is 3 - regular, and S is a - set the only possible graph of < V—S> = P5 or C5

Case 1: Let < V—S> = C5 = (v1, v2, v3, v4, v5)

Since G is 3 - regular, it is clearly verified that <S> ≠ K3 or or K1∪K2. Hence the only possible if <S> = P3 = (x, y, z). Since G is connected 3 - regular, y must be adjacent to any one of the vertex of C5. Let y be adjacent to v1, since G is 3 - regular, x is adjacent to any two of { v2, v5} or v2 (or v5) and v3(or v4). Let x be adjacent to v2 and v5. Then z is must be adjacent to v3 and v4, so that . If x is adjacent to {v2, v3}, then z is must be adjacent to v4 and v5. In this stage {x, v2} is - set, which is a contradiction. Hence no graph exists (Sivagnanam, 2012).

Case 2: < V—S> = P5 = (v1, v2, v3, v4, v5)

Since G is 3 - regular, it is clearly verified that <S>≠ K3 or . Hence <S> = K2∪K1 or P3.

Sub case (i) Let <S> = K2∪K1

Let xy be the edge in K2∪K1. Since G is connected let z be adjacent to both v1 and v5 and any one of {v2, v3, v4} or z is adjacent to v1(or v5) and any two of {v2, v3, v4} or z is adjacent to v2 and v3 and v4. Let z is adjacent to v1,v5 and v2. Then x is adjacent to v1 and v5 or x is adjacent to v1 and v3(or v4) or x is adjacent to v3 and v4 or x is adjacent to v5 and any one of {v3, v4}.

Sub case (ii) Let <S> = P3(x, y, z)

Since G is 3 - regular, y is adjacent to v1 (or v5) or any one of {v2, v3, v4}. If y is adjacent to v1, since G is 3 - regular, x is cannot be v1 and v5 and also x cannot be adjacent to v1 and any one {v2, v3, v4} and x cannot be adjacent to any two of {v2, v3, v4}, which is a contradiction. If y is adjacent to v3, then x cannot be adjacent to v1 and v3, and also x cannot be adjacent to v2 and v3, which is a contradiction. Hence no graph exists.

Three - Regular Graphs on 10 Vertices

Let G be a connected 3 - regular graph on 10 vertices for which . Let s = {x,y,z} be a complementary triple connected dominating set. Since G is 3 - regular, clearly <S> ≠ K3 and P3. Hence <S> = K1∪K2 or . Let <S1> = N(x) = {v1, v2, v3}. Let <S> = K1∪K2

Let yz be the edge in <S>. Let v4 and v5 be the vertices adjacent to y and v6 and v7 be adjacent to z. Let <S2> = { v4, v5} and<S3> = { v6, v7}. Then we will consider following three cases.

(i) <S1> = P3

<S1> =

<S1> = K2∪K1

Proposition: 3. 1

If <S> = K1∪K2 and <S1> = P3, then G is isomorphic to ςj for 1 ≤ j ≤ 3 (Fig. 3).

Proof:

Let <S1> = P3 ={v1, v2, v3}. We consider the following three cases.

Case1 <S2> = <S3> = K2

Case2 <S2> = K2 and <S3> =

Case3 <S2> =<S3> =

Case 1: <S2> = <S3> = K2

Since G is 3 - regular, v1 is adjacent to any one of { v4, v5, v6, v7}. Let v1 be adjacent to v4. Since G is 3 - regular, v3 cannot be adjacent to v5. Hence v3 is adjacent to any one of { v6, v7}. Let v3 be adjacent to v6. Hence v5 must be adjacent to v7 so that G ≅ G1

Case 2: <S2> = K2 and <S3> =

If v7 is adjacent to v4 and v5 or v1 and v3 or v1 (or v3) and v4(or v5). If v7 is adjacent to v4 and v5, then v6 is adjacent to v1 and v3 so that <V-S> is not triple connected, which is a contradiction. If v7 is adjacent to v1 and v3, then v6 is adjacent to v4 and v5 so that <V-S> is not triple connected, which is a contradiction. Hence v7 is adjacent to v1 and v4, then v6 is adjacent to v3 and v5 so that G ≅ G2

Case 3: <S2> =<S3> = G ≅ G3

Since G is 3 - regular, v1 is adjacent to any one of { v4, v5, v6, v7}. Let v1 is adjacent to v4. Since G is 3 - regular, v4 cannot be adjacent to v3. Hence v4 is adjacent to v6(or v7) and then v7 is adjacent to v3 and v5 and since G is 3 - regular, v5 is adjacent to v6 so that G ≅ G3

Proposition: 3.2

If <S> = K1∪K2 and <S1> = ςj, then G is isomorphic to ςj for 4 ≤ j ≤ 7 (Fig. 4).

Proof: We consider the following three cases.

Case 1: <S2> = <S3> = K2

<V-S> has seven vertices for which for which three vertices are of deg 1 and the remaining 4 are of degree 2. Within this is not possible to form a 3 - regular graph, Hence no graph exists.

Case 2: <S2> = K2 and <S3> =

v1 is adjacent to v4 and v5 (or) v6 and v7 (or) v4 (or v5) and v6(or v7). If v1 is adjacent to v4 and v5, then v2 is adjacent to v6 and v7 and then v3 is adjacent to v6 and v7. In this stage if we take S = { v4, v2, v7} with v2v7 ÃÂÃâE(G), then S is a dominating set. Let S1= {v5, y, v1}. Now, in this situation <S> = K1∪K2, <S1> = P3 which falls under proposition:3.1

If v1 is adjacent to v6 and v7, then v2 is adjacent to v4 and v5,(or) v6 and v7 (or) v4(or v5) and v6(or v7). If v2 is adjacent to v4 andv5, then v3 is adjacent to v6 and v7. In this stage if we take S = { v5,v1,v6} with v1v6 ÃÂÃâE(G), then S is a dominating set. Let S1= {y, v4, v2}. Now, in this situation <S> = K1∪K2, <S1> = P3 which falls under proposition:2.1. If v2 is adjacent to v4 andv6, then v3 is adjacent to v7 and v5 so that G ≅ G4.

v1 is adjacent to v4 and v6. Since G is 3 - regular, v2 is not adjacent to v5 and v6 and hence it must be adjacent to v5 and v7(or) v6 and v7. If v2 is adjacent to v5 and v7, then v3 is adjacent to v6 and v7 so that G ≅ G4.

Case 3: <S2> =<S3> =

Now v1 is adjacent to v4 and v5(or v6 and v7) or v4 and v6. If v1 is adjacent to v4 and v5, then since G is 3 - regular, v2 is not adjacent to v4 and v5. Hence v2 is adjacent to v6 and v7 or v4 (or v3) and v6(or v7).

If v2 is adjacent to v6 and v7, then v3 is not adjacent to v4 and v7. Also v3 is not adjacent v6 and v7. Hence v3 is adjacent to v4(or v5) and v6 (or v7) and then v7 is adjacent to v5 so that G ≅ G5. If v2 is adjacent v4 and v6, then v7 is adjacent to v5 and v3 and then v3 is adjacent to v6 so that G ≅ G6.

If v1 is adjacent to v6 and v4, then v2 is adjacent to v6 and v4 or v7 and v5 or v6 and v7(or v4 and v5) or v6 and v7 (or v7 and v4). If v2 is adjacent to v6 and v4,then v3 is adjacent v7 and v5 and then v5 is adjacent to v7 so that <V-S> is not triple connected, which is a contradiction.

If v2 is adjacent to v7 and v5, then v3 cannot be adjacent to v4 and v7 (or v6 and v7). Hence v3 is adjacent to v4 and v6 or v5 and v7 or v4 and v7 (or v6 and v7).

If v3 is adjacent is adjacent to v4 and v6, then v7 is adjacent to v5 so that <V-S> is not triple connected. If v3 is adjacent to v5 and v7, then v6 is adjacent to v4 so that <V-S> is not triple connected. If v3 is adjacent to v7 and v4, then v6 is adjacent to v5 so that G ≅ G6.

If v2 is adjacent to v6 and v5, then v3 cannot be adjacent to v4 and v5. Hence v3 is adjacent to v4 and v7 or v7 and v5. If v3 is adjacent to v7 and v4, then v7 is adjacent to v5 so that G ≅ G7. If v3 is adjacent to v5 and v7, then v7 is adjacent to v4 so that G ≅ G7.

If v2 is adjacent to v6 and v7, then v3 cannot be adjacent to v7 and v4. Also v3 is not adjacent to v7 and v5. Hence v3 is adjacent to v4 and v5 and then v5 is adjacent to v7 so that G ≅ G5.

Proposition: 3.3

If <S> = K1∪K2 and <S1> = K2∪K1, then G is isomorphic to ςj for 8 ≤ j ≤ 11 (Fig. 5).

Proof: Let v1 v2 be the edge in <S1>. We consider the following three cases.

Case 1: <S2> = <S3> = K2

Now, v3 is adjacent to v4 and v5 (or v6 and v7) or v6 and v4 (or v7 and v5). If v3 is adjacent to v4 and v5, then v2 is adjacent t to v6 (or v7) and then v1 is adjacent to v7. In this stage, if we take S = { v4, v2,v6} with v2v6 ε E(G), then S is a dominating set. Let S1 = (v5,y,v3}. Now in this situation <S>=K1∪K2, <S1>= P3 which follows under proposition 3.1 If v3 is adjacent to v6 and v4, then v1 is adjacent v7 (or v5) and then v2 is adjacent to v5 so that G ≅ G8.

Case 2: <S2> = K2 and <S3> =

Since G is 3 - regular, v3 cannot be adjacent to v4 and v5. Hence v3 is adjacent to v6 ( or v7) and v4(or v5) and v6 (or v5). If v3 is adjacent to v6 and v7, then v6 is adjacent to v1(or v2) or v4( or v5). If v6 is adjacent to v1, then v7 is not adjacent to v2 and hence v7 is adjacent to v4(or v5) and then v5 is adjacent to v2 so that G ≅ G9.

If v6 is adjacent to v4, then v7 is not adjacent to v5. Hence v7 is adjacent to v1(or v2) and then v2 is adjacent to v5 so that G ≅ G9. If v3 is adjacent to v4 and v6, then v7 is adjacent to v1 and v2 or v1(or v2) and v5. If v7 is adjacent to v1 and v2, then v6 is adjacent to v5. In this stage, if we take S = { v5, v6,v1} with v5v6 ε E(G), then S is a dominating set. Let S1 = (x,v2,v7}. Now in this situation <S> = K1 ∪ K2, <S1> = P3 which follows under proposition 3.1. If v7 is adjacent to v1 and v5, then v2 is adjacent to v6 so that G ≅ G10.

Case 3: <S2> =<S3> =

Now v3 is adjacent to v6 and v7(or v4 and v5) or v6 and v4(or v7 and v5). If v3 is adjacent to v6 and v7. In this stage, if we take S = {x, v3,y} with xv3 ε E(G), then S is a dominating set. Let S1 = (z,v4,v5}. Now in this situation <S> = K1∪K2, <S1> = G ≅ G11 which follows under proposition 3.2. If v3 is adjacent to v6 and v4, then v7 is not adjacent to v1 and v2. Hence v7 is adjacent to v4 and v5 or v1 and v4 or v1 and v5.

If v7 is adjacent to v4 and v5, then v5 is not adjacent to v6. Hence v5 is adjacent to v1(or v2) and then v2 is adjacent to v6. In this stage, if we take S = {v3,v6,v5} with v3v6 ÃÂÃâ E(G), then S is a dominating set. Let S1 = (y,v7,v1}. Now in this situation <S> = K1∪K2, <S1> = G ≅ G11 which follows under proposition 3.2. If v7 is adjacent to v1 and v4, then v5 is adjacent to v2 and v6 so that G ≅ G11.

If v7 is adjacent to v1 and v5, then v2 is not adjacent to v6. Hence v2 is adjacent to v4 and v5. If v2 is adjacent to v4, then v5 is adjacent to v6. In this stage, if we take S = {v7,v1,v4} with v7v1 ÃÂÃâ E(G), then S is a dominating set. Let S1 = (y,v3,v6}, S2 = (v5,z}, S3 = (v2,x}. Now in this situation <S> = K1∪K2, <S1> = K2∪K1, <S2> = and <S3> = K2 which falls under case 2.

Now we consider the graphs with <S> = . Then y can be adjacent to two of three vertices not in N[x]. If it is adjacent to two vertices say v4 and v5. Let S2 = {v4,v5}. Then z is adjacent to two vertices say v6 and v7. Let S3 = {v6,v7}. Then we will consider the following three situations.

(i) <S1> = P3

(ii) <S> = K2∪K1

<S1> =

Proposition 3. 4

If <S> = and <S1> = P3, then no new graph exists.

Proof: Let <S1> = P3 = (v1v2v3). We consider the following 3 cases.

Case 1: <S2> = <S3> = K2

Let U = S2∪{y} and V = S3∪{z}. Then <U> = <V> = C3. Since G is 3 - regular, for some u ÃÂÃâ U and v ÃÂÃâ V, uv ÃÂÃâ E(G). Then for S = {x,u,v} is a dominating set. Now in this situation <S> = K1∪K2, which falls under propositions <S> = K1∪K2.

Case 2: <S2> = K2 and <S3> =

Case 3: <S2> =<S3> =

Now y is adjacent to v1(or v3) or v6(or v7). In both cases no new graph exists.

Proposition 3. 5

If <S> = ςj and <S1> = K2∪yK1, then G is isomorphic to ςj for 11 ≤ j ≤ 13 (Fig. 6).

Proof: Let v1v2 be the edge in <S1>. We considers the following three cases.

Case 1: <S2> = <S3> = K2

Now v1 is adjacent to any one of {v4,v5,y}(or any one of{v6,v7,w}). Let v1 is adjacent to v4. Then no new graph exists.

Case 2: <S2> = K2 and <S3> =

Case 3: <S2> =<S3> =

Now v1 be adjacent to y(or z) or v4(or v5){or v6(or v7)}. In both cases no new graph exists.

Proposition: 3.6

If <S> = and <S1> = , then G is isomorphic to G14 (Fig. 7).

Proof: We consider the following three cases.

Case 1: <S2> = <S3> = K2

Let v4 v5 be the edge in <S2> and v6v7 be the edge in <S3>. Now v1 is adjacent to any two of {y,v4,v5} (or equivalently { z,v6,v7}) or any one of {y,v4,v5} and any one of{z,v6,v7}. In both cases no new graph exists.

Case 2: <S2> = K2 and <S3> =

Now z is adjacent to any one of {v1,v2,v3}. Let z be adjacent to v1. Then y is adjacent to v1 or not adjacent to v1. In both cases no new graph exists.

Case 3: <S2> =<S3> =

If v6 is adjacent to v2, then v1 is adjacent to v5 or v7. If v1 is adjacent to v5, then v3 is adjacent to v5 and v7, and then v2 is adjacent to v7 so that G ≅ G14. If v1 is adjacent to v7, then v3 is adjacent to v5 and v7, and then v2 is adjacent to v5 so that G ≅ G14. If z is adjacent to v5 or v2, then no new graph exists. If v1 is adjacent to y, then no new graph exists.

Theorem 3.7

Let G be a 3 - regular graph of order 10. Then , if and only if G is isomorphic to graphs ςj , 1 ≤ j ≤ 14

Proof

If G is any one of the graphs in figures in ςj, then clearly . Conversely, assume that . Then the proof follows from proposition 3.1 to 3.6

#### Conclusion

In this paper, we characterized the 3- regular graphs for which of order up to 10 vertices. The authors are also characterized 3-regular graphs for which of order 12 vertices which will be report in the subsequent papers.

#### Acknowledgment

This research work was supported by Departmental Special Assistance, university grant commission, New Delhi, India.

#### References

2. Haynes, T.W., Hedetniemi S.T. and Slater, P.J. (1998). Fundamentals of domination in graphs. Marcel Dekker. Inc., New York, USA.
3. Mahadevan, G., Selvam, A., Pualraj, J., Ayisha, B. and Subramanian, T. (2013). Complementary triple connected domination number of a graph. International Journal of Advances and applications in Discrete Mathematics. 12 : 39-54.
4. Paulraj, J.J., Angel, J.M.K., Chitra, D.P. and Sudhana, G. (2012). Triple connected graphs. Indian Journal of Mathematics and Mathematical Sciences. 8(1) : 61- 75.
5. Paulraj, J.J., Mahadevan, G. and Selvam, A. (2012). Triple connected domination number of a graph. International Journal of Mathematical Combinatorics. 3 : 93-104.
6. Sivagnanam, C. (2012). Double domination number and connectivity of a graph. International Journal of Digital Information and Wireless Communications. 2(1) : 40-45.