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.

**Mahadevan G ^{1*}, Iravithul Basira A^{2} and Sivagnanam C^{3}**

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

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

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

- *Corresponding Author:
- Mahadevan G

**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

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.

Domination number, Complementary triple connected domination number, Chromatic number

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.

**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ÃÂ¢ÃÅ¸ÃÂ© ≠ K_{3} ,K_{2}UK_{1}. Hence <V—S> = K_{3} or P_{3}. Let <V— S> = K_{3} or P_{3}. Then the possible case of <S> = K_{3}, P_{3}. 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 = { v_{1}, v_{2}, v_{3}, v_{4}, v_{5}}. <S> = K_{3} or or K_{1}UK_{2} or P_{3} and, , K_{5}, W_{5}, F_{2},, K_{5}-{e},, , C_{3}(P_{3}), C_{3}(2P_{2}), C_{3}(P_{2},P_{2},0) and the following (Fig. 2).

Since G is 3 - regular, and S is a - set the only possible graph of < V—S> = P_{5} or C_{5}

**Case 1:** Let < V—S> = C_{5} = (v_{1}, v_{2}, v_{3}, v_{4}, v_{5})

Since G is 3 - regular, it is clearly verified that <S> ≠ K_{3} or or K_{1}∪K_{2}. Hence the only possible if <S> = P_{3} = (x, y, z). Since G is connected 3 - regular, y must be adjacent to any one of the vertex of C_{5}. Let y be adjacent to v_{1}, since G is 3 - regular, x is adjacent to any two of { v_{2}, v_{5}} or v_{2} (or v_{5}) and v_{3}(or v_{4}). Let x be adjacent to v_{2} and v_{5}. Then z is must be adjacent to v_{3} and v_{4}, so that . If x is adjacent to {v_{2}, v_{3}}, then z is must be adjacent to v_{4} and v_{5}. In this stage {x, v_{2}} is - set, which is a contradiction. Hence no graph exists (Sivagnanam, 2012).

**Case 2:** < V—S> = P_{5} = (v_{1}, v_{2}, v_{3}, v_{4}, v_{5})

Since G is 3 - regular, it is clearly verified that <S>≠ K_{3} or . Hence <S> = K_{2}∪K_{1} or P_{3}.

**Sub case (i)** Let <S> = K_{2}∪K_{1}

Let xy be the edge in K_{2}∪K_{1}. Since G is connected let z be adjacent to both v_{1} and v_{5} and any one of {v_{2}, v_{3}, v_{4}} or z is adjacent to v_{1}(or v_{5}) and any two of {v_{2}, v_{3}, v_{4}} or z is adjacent to v_{2} and v_{3} and v_{4}. Let z is adjacent to v_{1},v_{5} and v_{2}. Then x is adjacent to v_{1} and v_{5} or x is adjacent to v_{1} and v_{3}(or v_{4}) or x is adjacent to v_{3} and v_{4} or x is adjacent to v_{5} and any one of {v_{3}, v_{4}}.

If x is adjacent to v_{1} and v_{5}, then y must be adjacent to v_{3} and v_{4}. In this stage {v_{1}, v_{4}} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v_{1} and v_{3} and then y must be adjacent to v_{4} and v_{5}. In this stage {v_{1}, v_{4}} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v_{3} and v_{4}, then y must be adjacent to v_{5} and v_{1}. In this stage {v_{1}, v_{4}} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v_{5} and v_{3}, then y must be adjacent to v_{4} and v_{1} so that .

Let z be adjacent to v_{1}, v_{2}, v_{3}. Then x is adjacent to v_{4} and v_{5} or v_{1} and v_{4} or v_{1} and v_{5}. If x is adjacent to v_{4} and v_{5}, then y must be adjacent to v_{1} and v_{5}. In this stage {v_{5}, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. If x is adjacent to v_{1} and v_{4}, then y must be adjacent to v_{5}, since G is 3 - regular, which is a contradiction. If x is adjacent to v_{1} and v_{5}, then y must be adjacent to v_{4} and v_{5}. In this stage {y, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. Let z be adjacent to v_{2}, v_{3}and v_{4}. Since G is 3 - regular, x be adjacent to v_{1} and v_{5}, which is a contradiction.

**Sub case (ii)** Let <S> = P_{3}(x, y, z)

Since G is 3 - regular, y is adjacent to v_{1} (or v_{5}) or any one of {v_{2}, v_{3}, v_{4}}. If y is adjacent to v_{1}, since G is 3 - regular, x is cannot be v_{1} and v_{5} and also x cannot be adjacent to v_{1} and any one {v_{2}, v_{3}, v_{4}} and x cannot be adjacent to any two of {v_{2}, v_{3}, v_{4}}, which is a contradiction. If y is adjacent to v_{3}, then x cannot be adjacent to v_{1} and v_{3}, and also x cannot be adjacent to v_{2} and v_{3}, 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> ≠ K_{3} and P_{3}. Hence <S> = K_{1}∪K_{2} or . Let <S_{1}> = N(x) = {v_{1}, v_{2}, v_{3}}. Let <S> = K_{1}∪K_{2}

Let yz be the edge in <S>. Let v_{4} and v_{5} be the vertices adjacent to y and v_{6} and v_{7} be adjacent to z. Let <S_{2}> = { v_{4}, v_{5}} and<S_{3}> = { v_{6}, v_{7}}. Then we will consider following three cases.

(i) <S_{1}> = P_{3}

<S_{1}> =

<S_{1}> = K_{2}∪K_{1}

**Proposition: 3. 1**

If <S> = K_{1}∪K_{2} and <S_{1}> = P_{3}, then G is isomorphic to *ς _{j}* for 1 ≤ j ≤ 3 (Fig. 3).

**Proof:**

Let <S_{1}> = P_{3} ={v_{1}, v_{2}, v_{3}}. We consider the following three cases.

Case1 <S_{2}> = <S_{3}> = K_{2}

Case2 <S_{2}> = K_{2} and <S_{3}> =

Case3 <S_{2}> =<S_{3}> =

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

Since G is 3 - regular, v_{1} is adjacent to any one of { v_{4}, v_{5}, v_{6}, v_{7}}. Let v_{1} be adjacent to v_{4}. Since G is 3 - regular, v_{3} cannot be adjacent to v_{5}. Hence v_{3} is adjacent to any one of { v_{6}, v_{7}}. Let v_{3} be adjacent to v_{6}. Hence v_{5} must be adjacent to v_{7} so that G ≅ G_{1}

**Case 2:** <S_{2}> = K_{2} and <S_{3}> =

If v_{7} is adjacent to v_{4} and v_{5} or v_{1} and v_{3} or v_{1} (or v_{3}) and v_{4}(or v_{5}). If v_{7} is adjacent to v_{4} and v_{5}, then v_{6} is adjacent to v_{1} and v_{3} so that <V-S> is not triple connected, which is a contradiction. If v_{7} is adjacent to v_{1} and v_{3}, then v_{6} is adjacent to v_{4} and v_{5} so that <V-S> is not triple connected, which is a contradiction. Hence v_{7} is adjacent to v_{1} and v_{4}, then v_{6} is adjacent to v_{3} and v_{5} so that G ≅ G_{2}

**Case 3:** <S_{2}> =<S_{3}> = G ≅ G_{3}

Since G is 3 - regular, v_{1} is adjacent to any one of { v_{4}, v_{5}, v_{6}, v_{7}}. Let v_{1} is adjacent to v_{4}. Since G is 3 - regular, v_{4} cannot be adjacent to v_{3}. Hence v_{4} is adjacent to v_{6}(or v_{7}) and then v_{7} is adjacent to v_{3} and v_{5} and since G is 3 - regular, v_{5} is adjacent to v_{6} so that G ≅ G_{3}

**Proposition: 3.2**

If <S> = K_{1}∪K_{2} and <S_{1}> = ς_{j}, then G is isomorphic to ς_{j} for 4 ≤ j ≤ 7 (Fig. 4).

**Proof:** We consider the following three cases.

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

<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:** <S_{2}> = K_{2} and <S_{3}> =

v_{1} is adjacent to v_{4} and v_{5} (or) v_{6} and v_{7} (or) v_{4} (or v_{5}) and v_{6}(or v_{7}). If v_{1} is adjacent to v_{4} and v_{5}, then v_{2} is adjacent to v_{6} and v_{7} and then v_{3} is adjacent to v_{6} and v_{7}. In this stage if we take S = { v_{4}, v_{2}, v_{7}} with v_{2}v_{7} ÃÂÃâE(G), then S is a dominating set. Let S_{1}= {v_{5}, y, v_{1}}. Now, in this situation <S> = K_{1}∪K_{2}, <S_{1}> = P_{3} which falls under proposition:3.1

If v_{1} is adjacent to v_{6} and v_{7}, then v_{2} is adjacent to v_{4} and v_{5},(or) v_{6} and v_{7} (or) v_{4}(or v_{5}) and v_{6}(or v_{7}). If v_{2} is adjacent to v_{4} andv_{5}, then v_{3} is adjacent to v_{6} and v_{7}. In this stage if we take S = { v_{5},v_{1},v_{6}} with v_{1}v_{6} ÃÂÃâE(G), then S is a dominating set. Let S_{1}= {y, v_{4}, v_{2}}. Now, in this situation <S> = K_{1}∪K_{2}, <S_{1}> = P_{3} which falls under proposition:2.1. If v_{2} is adjacent to v_{4} andv_{6}, then v_{3} is adjacent to v_{7} and v_{5} so that G ≅ G_{4}.

v_{1} is adjacent to v_{4} and v_{6}. Since G is 3 - regular, v_{2} is not adjacent to v_{5} and v_{6} and hence it must be adjacent to v_{5} and v_{7}(or) v_{6} and v_{7}. If v_{2} is adjacent to v_{5} and v_{7}, then v_{3} is adjacent to v_{6} and v_{7} so that G ≅ G_{4}.

**Case 3:** <S_{2}> =<S_{3}> =

Now v_{1} is adjacent to v_{4} and v_{5}(or v_{6} and v_{7}) or v_{4} and v_{6}. If v_{1} is adjacent to v_{4} and v_{5}, then since G is 3 - regular, v_{2} is not adjacent to v_{4} and v_{5}. Hence v_{2} is adjacent to v_{6} and v_{7} or v_{4} (or v_{3}) and v_{6}(or v_{7}).

If v_{2} is adjacent to v_{6} and v_{7}, then v_{3} is not adjacent to v_{4} and v_{7}. Also v_{3} is not adjacent v_{6} and v_{7}. Hence v_{3} is adjacent to v_{4}(or v_{5}) and v_{6} (or v_{7}) and then v_{7} is adjacent to v_{5} so that G ≅ G_{5}. If v_{2} is adjacent v_{4} and v_{6}, then v_{7} is adjacent to v_{5} and v_{3} and then v_{3} is adjacent to v_{6} so that G ≅ G_{6}.

If v_{1} is adjacent to v_{6} and v_{4}, then v_{2} is adjacent to v_{6} and v_{4} or v_{7} and v_{5} or v_{6} and v_{7}(or v_{4} and v_{5}) or v_{6} and v_{7} (or v_{7} and v_{4}). If v_{2} is adjacent to v_{6} and v_{4},then v_{3} is adjacent v_{7} and v_{5} and then v_{5} is adjacent to v_{7} so that <V-S> is not triple connected, which is a contradiction.

If v_{2} is adjacent to v_{7} and v_{5}, then v_{3} cannot be adjacent to v_{4} and v_{7} (or v_{6} and v_{7}). Hence v_{3} is adjacent to v_{4} and v_{6} or v_{5} and v_{7} or v_{4} and v_{7} (or v_{6} and v_{7}).

If v_{3} is adjacent is adjacent to v_{4} and v_{6}, then v_{7} is adjacent to v_{5} so that <V-S> is not triple connected. If v_{3} is adjacent to v_{5} and v_{7}, then v_{6} is adjacent to v_{4} so that <V-S> is not triple connected. If v_{3} is adjacent to v_{7} and v_{4}, then v_{6} is adjacent to v_{5} so that G ≅ G_{6}.

If v_{2} is adjacent to v_{6} and v_{5}, then v_{3} cannot be adjacent to v_{4} and v_{5}. Hence v_{3} is adjacent to v_{4} and v_{7} or v_{7} and v_{5}. If v_{3} is adjacent to v_{7} and v_{4}, then v_{7} is adjacent to v_{5} so that G ≅ G_{7}. If v_{3} is adjacent to v_{5} and v_{7}, then v_{7} is adjacent to v_{4} so that G ≅ G_{7}.

If v_{2} is adjacent to v_{6} and v_{7}, then v_{3} cannot be adjacent to v_{7} and v_{4}. Also v_{3} is not adjacent to v_{7} and v_{5}. Hence v_{3} is adjacent to v_{4} and v_{5} and then v_{5} is adjacent to v_{7} so that G ≅ G_{5}.

**Proposition: 3.3**

If <S> = K_{1}∪K_{2} and <S_{1}> = K_{2}∪K_{1}, then G is isomorphic to *ς _{j}* for 8 ≤ j ≤ 11 (Fig. 5).

**Proof:** Let v_{1} v_{2} be the edge in <S_{1}>. We consider the following three cases.

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

Now, v_{3} is adjacent to v_{4} and v_{5} (or v_{6} and v_{7}) or v_{6} and v_{4} (or v_{7} and v_{5}). If v_{3} is adjacent to v_{4} and v_{5}, then v_{2} is adjacent t to v_{6} (or v_{7}) and then v_{1} is adjacent to v_{7}. In this stage, if we take S = { v_{4}, v_{2},v_{6}} with v_{2}v_{6} ε E(G), then S is a dominating set. Let S_{1} = (v_{5},y,v_{3}}. Now in this situation <S>=K_{1}∪K_{2}, <S_{1}>= P_{3} which follows under proposition 3.1 If v_{3} is adjacent to v_{6} and v_{4}, then v_{1} is adjacent v_{7} (or v_{5}) and then v_{2} is adjacent to v_{5} so that G ≅ G_{8}.

**Case 2:** <S_{2}> = K_{2} and <S_{3}> =

Since G is 3 - regular, v_{3} cannot be adjacent to v_{4} and v_{5}. Hence v_{3} is adjacent to v_{6} ( or v_{7}) and v_{4}(or v_{5}) and v_{6} (or v_{5}). If v_{3} is adjacent to v_{6} and v_{7}, then v_{6} is adjacent to v_{1}(or v_{2}) or v_{4}( or v_{5}). If v_{6} is adjacent to v_{1}, then v_{7} is not adjacent to v_{2} and hence v_{7} is adjacent to v_{4}(or v_{5}) and then v_{5} is adjacent to v_{2} so that G ≅ G_{9}.

If v_{6} is adjacent to v_{4}, then v_{7} is not adjacent to v_{5}. Hence v_{7} is adjacent to v_{1}(or v_{2}) and then v_{2} is adjacent to v_{5} so that G ≅ G_{9}. If v_{3} is adjacent to v_{4} and v_{6}, then v_{7} is adjacent to v_{1} and v_{2} or v_{1}(or v_{2}) and v_{5}. If v_{7} is adjacent to v_{1} and v_{2}, then v_{6} is adjacent to v_{5}. In this stage, if we take S = { v_{5}, v_{6},v_{1}} with v_{5}v_{6} ε E(G), then S is a dominating set. Let S_{1} = (x,v_{2},v_{7}}. Now in this situation <S> = K_{1} ∪ K_{2}, <S_{1}> = P_{3} which follows under proposition 3.1. If v_{7} is adjacent to v_{1} and v_{5}, then v_{2} is adjacent to v_{6} so that G ≅ G_{10}.

**Case 3:** <S_{2}> =<S_{3}> =

Now v_{3} is adjacent to v_{6} and v_{7}(or v_{4} and v_{5}) or v_{6} and v_{4}(or v_{7} and v_{5}). If v_{3} is adjacent to v_{6} and v_{7}. In this stage, if we take S = {x, v_{3},y} with xv_{3} ε E(G), then S is a dominating set. Let S_{1} = (z,v_{4},v_{5}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = G ≅ G_{11} which follows under proposition 3.2. If v_{3} is adjacent to v_{6} and v_{4}, then v_{7} is not adjacent to v_{1} and v_{2}. Hence v_{7} is adjacent to v_{4} and v_{5} or v_{1} and v_{4} or v_{1} and v_{5}.

If v_{7} is adjacent to v_{4} and v_{5}, then v_{5} is not adjacent to v_{6}. Hence v_{5} is adjacent to v_{1}(or v_{2}) and then v_{2} is adjacent to v_{6}. In this stage, if we take S = {v_{3},v_{6},v_{5}} with v_{3}v_{6} ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (y,v_{7},v_{1}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = G ≅ G_{11} which follows under proposition 3.2. If v_{7} is adjacent to v_{1} and v_{4}, then v_{5} is adjacent to v_{2} and v_{6} so that G ≅ G_{11}.

If v_{7} is adjacent to v_{1} and v_{5}, then v_{2} is not adjacent to v_{6}. Hence v_{2} is adjacent to v_{4} and v_{5}. If v_{2} is adjacent to v_{4}, then v_{5} is adjacent to v_{6}. In this stage, if we take S = {v_{7},v_{1},v_{4}} with v_{7}v_{1} ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (y,v_{3},v_{6}}, S_{2} = (v_{5},z}, S_{3} = (v_{2},x}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = K_{2}∪K_{1}, <S_{2}> = and <S_{3}> = K_{2} 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 v_{4} and v_{5}. Let S_{2} = {v_{4},v_{5}}. Then z is adjacent to two vertices say v_{6} and v_{7}. Let S_{3} = {v_{6},v_{7}}. Then we will consider the following three situations.

(i) <S_{1}> = P_{3}

(ii) <S> = K_{2}∪K_{1}

<S_{1}> =

**Proposition 3. 4**

If <S> = and <S_{1}> = P_{3}, then no new graph exists.

**Proof:** Let <S_{1}> = P_{3} = (v_{1}v_{2}v_{3}). We consider the following 3 cases.

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

Let U = S_{2}∪{y} and V = S_{3}∪{z}. Then <U> = <V> = C_{3}. 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> = K_{1}∪K_{2}, which falls under propositions <S> = K_{1}∪K_{2}.

**Case 2:** <S_{2}> = K_{2} and <S_{3}> =

Let v_{4} and v_{5} be the edge in S_{2}. Since G is 3 - regular y cannot be adjacent to v_{1}(or v_{3}). Hence y is adjacent to v_{6} (or v_{7}). If y is adjacent to v_{6}(or v_{7}), then v_{7} is adjacent v_{1} and v_{3} or v_{5} and v_{4} or v_{4}(or v_{5}) and v_{1}(or v_{3}). If v_{7} is adjacent to v_{1} and v_{3}, then v_{6} is adjacent to v_{4}(or v_{5}) and then z is adjacent to v_{5}. In this situation if we take S = {x,v_{5},z} with v_{5}z ÃÂÃâ E(G) then S is a dominating set. Let S_{1} = {v_{1},v_{2},v_{3}}. Now in this situation <S> = K_{1} K_{2}, <S_{1}> = P_{3} which falls under proposition 3.1. If v_{7} is adjacent v_{1} and v_{4}, then v_{5} is not adjacent v_{3}. Hence v_{5} is adjacent to v_{6} or z. If v_{5} is adjacent to v_{6}, then z is adjacent to v_{3} so that <V S> is not triple connected, which is a contradiction. If v_{5} is adjacent to z, then v_{3} is adjacent to v_{6}. In this stage, if we take S = { x, v_{5},z} with v_{5}z ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (v_{1},v_{2},v_{3}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = P_{3} which follows under proposition 3.1. If v_{7} is adjacent to v_{5} and v_{4}, then v_{6} is adjacent to v_{1}(or v_{3}) and z is adjacent to v_{3} so that <V—S> is not triple connected, which is a contradiction.

**Case 3:** <S_{2}> =<S_{3}> =

Now y is adjacent to v_{1}(or v_{3}) or v_{6}(or v_{7}). In both cases no new graph exists.

**Proposition 3. 5**

If <S> = *ς _{j}* and <S

**Proof:** Let v_{1}v_{2} be the edge in <S_{1}>. We considers the following three cases.

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

Now v_{1} is adjacent to any one of {v_{4},v_{5},y}(or any one of{v_{6},v_{7},w}). Let v_{1} is adjacent to v_{4}. Then no new graph exists.

**Case 2:** <S_{2}> = K_{2} and <S_{3}> =

Now v_{1} is adjacent to any one of {y,v_{4},v_{5}} or z or v_{6} (or v_{7}). If v_{1} is adjacent to y, then z is adjacent to v_{3} or v_{4}(or v_{5}) or v_{2}. Let z is adjacent to v_{3}. In this stage, if we take S = { z,v_{1},y} with v_{1}y E(G), then S is a dominating set. Let S_{1} = (v_{3},v_{6},v_{7}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = which follows under proposition 3.2. If z is adjacent to v_{4}. In this stage, if we take S = { x,v_{4},z} with v_{4}z ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (v_{1},v_{2},v_{3}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = K_{1}∪K_{2} which follows under proposition: 3.3. If z is adjacent to v_{2}, then v_{5} is adjacent to v_{3} or v_{6}(or v_{7}). Let v_{5} is adjacent to v_{3}. In this stage, if we take S = { v_{5},v_{2},z} with v_{2}z ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (v_{3},v_{4},y}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = K_{1}∪K_{2} which follows under proposition 3.3. If v_{5} is adjacent to v_{6}, then v_{7} is adjacent to v_{3} and v_{4}, and then v_{3} is adjacent to v_{6} so that G ≅ G_{12}. If v_{1} is adjacent to z, then no new graph exists. If v_{1} is adjacent to v_{6}, then v_{6} is adjacent to any one of{y,v_{4},v_{5}} or v_{3} or v_{2}. If v_{6} is adjacent to y, then z is adjacent to v_{3} or v_{2} or v_{4} (or v_{5}). If z is adjacent to v_{3}, then v_{2} is adjacent to v_{4} (or v_{5}) or v_{7}. If v_{2} is adjacent to v_{4}, then v_{7} is adjacent to v_{3} and v_{5}. In this stage, if we take S = { y,v_{3},x} with v_{3}x ÃÂÃâ E(G), then S is a dominating set. Let S_{1} = (v_{4},v_{5},v_{6}}. Now in this situation <S> = K_{1}∪K_{2}, <S_{1}> = K_{1}∪K_{2} which follows under proposition 3.3. If v_{2} is adjacent to v_{7}, then since G is 3 - regular v_{7} cannot be adjacent to v_{3}. Hence v_{7} must be adjacent to v_{4} (or v_{5}) and then v_{3} is adjacent to v_{5} so that G ≅ G_{13}. If z is adjacent to v_{2} or v_{4}, then no new graph exists. If v_{6} is adjacent to v_{3} or v_{2}, then no new graph exists.

**Case 3:** <S_{2}> =<S_{3}> =

Now v_{1} be adjacent to y(or z) or v_{4}(or v_{5}){or v_{6}(or v_{7})}. In both cases no new graph exists.

**Proposition: 3.6**

If <S> = and <S_{1}> = , then G is isomorphic to G_{14} (Fig. 7).

**Proof:** We consider the following three cases.

**Case 1:** <S_{2}> = <S_{3}> = K_{2}

Let v_{4} v_{5} be the edge in <S_{2}> and v_{6}v_{7} be the edge in <S_{3}>. Now v_{1} is adjacent to any two of {y,v_{4},v_{5}} (or equivalently { z,v_{6},v_{7}}) or any one of {y,v_{4},v_{5}} and any one of{z,v_{6},v_{7}}. In both cases no new graph exists.

**Case 2:** <S_{2}> = K_{2} and <S_{3}> =

Now z is adjacent to any one of {v_{1},v_{2},v_{3}}. Let z be adjacent to v_{1}. Then y is adjacent to v_{1} or not adjacent to v_{1}. In both cases no new graph exists.

**Case 3:** <S_{2}> =<S_{3}> =

Now v_{1} is adjacent to v_{4} ( or v_{5}) or v_{1} is adjacent to y (or z). If v_{1} is adjacent to v_{4}, then y is adjacent to v_{1} or v_{2} (or v_{7}). If y is adjacent to v_{1}. In this stage, if we take S = { y,x,z}, then S is a dominating set. Let S_{1} = (v_{1},v_{4},v_{5}}. Now in this situation <S> = , ,<S> = K_{1}∪K_{2} which follows under proposition 3.5. If y is adjacent to v_{2}, then z is adjacent to v_{2} or v_{1}(or v_{4}) or v_{3} (or v_{5}). If z is adjacent v_{2}, then v_{6} is adjacent to v_{3} and v_{5} or v_{1} and v_{4} or v_{3} (or v_{5}) and v_{1}( or v_{4}). If v_{6} is adjacent to v_{3} and v_{5}, then v_{4} is adjacent to v_{3} or v_{7}. If v_{4} is adjacent to v_{3}, then v_{7} is adjacent to v_{1} and v_{5} so that <V—S> is not triple connected, which is a contradiction.

If v_{4} is adjacent to v_{7}, then v_{1} is adjacent to v_{5} or v_{7}, then v_{1} is adjacent to v_{5} or v_{7}. If v_{1} is adjacent to v_{5}, then v_{3} is adjacent to v_{7} so that<V—S> is not triple connected, which is a contradiction. If v_{1} is adjacent to v_{7}, then v_{3} is adjacent to v_{5}. In this stage, if we take S = { v_{3},v_{2},v_{4}}, then S is a dominating set. Let S_{1} = (x,v_{5},v_{6}}. Now in this situation <S> = , <S_{1}> = K_{1}∪K_{2} which follows under proposition 3.5. If v_{6} is adjacent to v_{1} and v_{4}, then v_{5} is adjacent to v_{3} and v_{7} and then v_{3} is adjacent to v_{7}. In this stage, if we take S = { v_{2},v_{4},v_{3}}, then S is a dominating set. Let S_{1} = (y,v_{1},v_{6}}. Now in this situation <S> = , <S_{1}> = K_{1}∪K_{2} which follows under proposition 3.5. If v_{6} is adjacent to v_{3} and v_{1}, then v_{5} is adjacent to v_{3} and v_{7}, and then v_{7} is adjacent to v_{4} so that <V—S> is not triple connected, which is a contradiction. If z is adjacent to v_{1} or v_{3}, then no new graph exists. If y is adjacent to v_{6}, then z is adjacent to v_{1} or v_{4} or v_{5} or v_{2}(or v_{3}). If z is adjacent to v_{1}, then no new graph exists. If z is adjacent to v_{4}, then v_{6} is adjacent to v_{1} or v_{2}(or v_{3}). If v_{6} is adjacent to v_{1}, then v_{2} is adjacent to v_{5} and v_{7} and then v_{3} is adjacent to v_{5} and v_{7} so that <V—S> is not triple connected, which is a contradiction.

If v_{6} is adjacent to v_{2}, then v_{1} is adjacent to v_{5} or v_{7}. If v_{1} is adjacent to v_{5}, then v_{3} is adjacent to v_{5} and v_{7}, and then v_{2} is adjacent to v_{7} so that G ≅ G_{14}. If v_{1} is adjacent to v_{7}, then v_{3} is adjacent to v_{5} and v_{7}, and then v_{2} is adjacent to v_{5} so that G ≅ G_{14}. If z is adjacent to v_{5} or v_{2}, then no new graph exists. If v_{1} 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

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.

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

- Harary, F. (1972). Graph theory.
*Addison Wesley Reading Mass*. - Haynes, T.W., Hedetniemi S.T. and Slater, P.J. (1998). Fundamentals of domination in graphs. Marcel Dekker. Inc., New York, USA.
- 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. - 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. - Paulraj, J.J., Mahadevan, G. and Selvam, A. (2012). Triple connected domination number of a graph.
*International Journal of Mathematical Combinatorics.*3 : 93-104. - Sivagnanam, C. (2012). Double domination number and connectivity of a graph.
*International Journal of Digital Information and Wireless Communications*. 2(1) : 40-45.

Copyright © 2024 Research and Reviews, All Rights Reserved