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

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) image.

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 image

Let G = (V,E) be a connected 3 - regular graph of order p with image andimage. We consider 3 - regular graph for whichimage. image which givesimage, p ≤ 12. Since ( ) 3 image 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 image. Since image, 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 imageor K1UK2 or P3 andimage, image, image K5, W5, F2,, K5-{e},image, image, C3(P3), C3(2P2), C3(P2,P2,0) and the following (Fig. 2).

Since G is 3 - regular, and S is a image - 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 image 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 image. If x is adjacent to {v2, v3}, then z is must be adjacent to v4 and v5. In this stage {x, v2} is image - 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 image. 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}.

If x is adjacent to v1 and v5, then y must be adjacent to v3 and v4. In this stage {v1, v4} be a image - set, which is a contradiction. Hence no graph exists. If x is adjacent to v1 and v3 and then y must be adjacent to v4 and v5. In this stage {v1, v4} be a image - set, which is a contradiction. Hence no graph exists. If x is adjacent to v3 and v4, then y must be adjacent to v5 and v1. In this stage {v1, v4} be a image - set, which is a contradiction. Hence no graph exists. If x is adjacent to v5 and v3, then y must be adjacent to v4 and v1 so that image.

Let z be adjacent to v1, v2, v3. Then x is adjacent to v4 and v5 or v1 and v4 or v1 and v5. If x is adjacent to v4 and v5, then y must be adjacent to v1 and v5. In this stage {v5, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. If x is adjacent to v1 and v4, then y must be adjacent to v5, since G is 3 - regular, which is a contradiction. If x is adjacent to v1 and v5, then y must be adjacent to v4 and v5. In this stage {y, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. Let z be adjacent to v2, v3and v4. Since G is 3 - regular, x be adjacent to v1 and v5, which is a contradiction.

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 image. 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 image. 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> = image

<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> = image

Case3 <S2> =<S3> = image

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> = image

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> = image

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> = image

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> = image

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> = image

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> = image and <S3> = K2 which falls under case 2.

Now we consider the graphs with <S> = image. 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> = image

Proposition 3. 4

If <S> = image 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> = image

Let v4 and v5 be the edge in S2. Since G is 3 - regular y cannot be adjacent to v1(or v3). Hence y is adjacent to v6 (or v7). If y is adjacent to v6(or v7), then v7 is adjacent v1 and v3 or v5 and v4 or v4(or v5) and v1(or v3). If v7 is adjacent to v1 and v3, then v6 is adjacent to v4(or v5) and then z is adjacent to v5. In this situation if we take S = {x,v5,z} with v5z Є E(G) then S is a dominating set. Let S1 = {v1,v2,v3}. Now in this situation <S> = K1 K2, <S1> = P3 which falls under proposition 3.1. If v7 is adjacent v1 and v4, then v5 is not adjacent v3. Hence v5 is adjacent to v6 or z. If v5 is adjacent to v6, then z is adjacent to v3 so that <V S> is not triple connected, which is a contradiction. If v5 is adjacent to z, then v3 is adjacent to v6. In this stage, if we take S = { x, v5,z} with v5z Є E(G), then S is a dominating set. Let S1 = (v1,v2,v3}. Now in this situation <S> = K1∪K2, <S1> = P3 which follows under proposition 3.1. If v7 is adjacent to v5 and v4, then v6 is adjacent to v1(or v3) and z is adjacent to v3 so that <V—S> is not triple connected, which is a contradiction.

Case 3: <S2> =<S3> = image

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> = image

Now v1 is adjacent to any one of {y,v4,v5} or z or v6 (or v7). If v1 is adjacent to y, then z is adjacent to v3 or v4(or v5) or v2. Let z is adjacent to v3. In this stage, if we take S = { z,v1,y} with v1y E(G), then S is a dominating set. Let S1 = (v3,v6,v7}. Now in this situation <S> = K1∪K2, <S1> = image which follows under proposition 3.2. If z is adjacent to v4. In this stage, if we take S = { x,v4,z} with v4z Є E(G), then S is a dominating set. Let S1 = (v1,v2,v3}. Now in this situation <S> = K1∪K2, <S1> = K1∪K2 which follows under proposition: 3.3. If z is adjacent to v2, then v5 is adjacent to v3 or v6(or v7). Let v5 is adjacent to v3. In this stage, if we take S = { v5,v2,z} with v2z Є E(G), then S is a dominating set. Let S1 = (v3,v4,y}. Now in this situation <S> = K1∪K2, <S1> = K1∪K2 which follows under proposition 3.3. If v5 is adjacent to v6, then v7 is adjacent to v3 and v4, and then v3 is adjacent to v6 so that G ≅ G12. If v1 is adjacent to z, then no new graph exists. If v1 is adjacent to v6, then v6 is adjacent to any one of{y,v4,v5} or v3 or v2. If v6 is adjacent to y, then z is adjacent to v3 or v2 or v4 (or v5). If z is adjacent to v3, then v2 is adjacent to v4 (or v5) or v7. If v2 is adjacent to v4, then v7 is adjacent to v3 and v5. In this stage, if we take S = { y,v3,x} with v3x Є E(G), then S is a dominating set. Let S1 = (v4,v5,v6}. Now in this situation <S> = K1∪K2, <S1> = K1∪K2 which follows under proposition 3.3. If v2 is adjacent to v7, then since G is 3 - regular v7 cannot be adjacent to v3. Hence v7 must be adjacent to v4 (or v5) and then v3 is adjacent to v5 so that G ≅ G13. If z is adjacent to v2 or v4, then no new graph exists. If v6 is adjacent to v3 or v2, then no new graph exists.

Case 3: <S2> =<S3> = image

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> = image and <S1> = image, 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> = image

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> = image

Now v1 is adjacent to v4 ( or v5) or v1 is adjacent to y (or z). If v1 is adjacent to v4, then y is adjacent to v1 or v2 (or v7). If y is adjacent to v1. In this stage, if we take S = { y,x,z}, then S is a dominating set. Let S1 = (v1,v4,v5}. Now in this situation <S> = image, ,<S> = K1∪K2 which follows under proposition 3.5. If y is adjacent to v2, then z is adjacent to v2 or v1(or v4) or v3 (or v5). If z is adjacent v2, then v6 is adjacent to v3 and v5 or v1 and v4 or v3 (or v5) and v1( or v4). If v6 is adjacent to v3 and v5, then v4 is adjacent to v3 or v7. If v4 is adjacent to v3, then v7 is adjacent to v1 and v5 so that <V—S> is not triple connected, which is a contradiction.

If v4 is adjacent to v7, then v1 is adjacent to v5 or v7, then v1 is adjacent to v5 or v7. If v1 is adjacent to v5, then v3 is adjacent to v7 so that<V—S> is not triple connected, which is a contradiction. If v1 is adjacent to v7, then v3 is adjacent to v5. In this stage, if we take S = { v3,v2,v4}, then S is a dominating set. Let S1 = (x,v5,v6}. Now in this situation <S> = image, <S1> = K1∪K2 which follows under proposition 3.5. If v6 is adjacent to v1 and v4, then v5 is adjacent to v3 and v7 and then v3 is adjacent to v7. In this stage, if we take S = { v2,v4,v3}, then S is a dominating set. Let S1 = (y,v1,v6}. Now in this situation <S> = image, <S1> = K1∪K2 which follows under proposition 3.5. If v6 is adjacent to v3 and v1, then v5 is adjacent to v3 and v7, and then v7 is adjacent to v4 so that <V—S> is not triple connected, which is a contradiction. If z is adjacent to v1 or v3, then no new graph exists. If y is adjacent to v6, then z is adjacent to v1 or v4 or v5 or v2(or v3). If z is adjacent to v1, then no new graph exists. If z is adjacent to v4, then v6 is adjacent to v1 or v2(or v3). If v6 is adjacent to v1, then v2 is adjacent to v5 and v7 and then v3 is adjacent to v5 and v7 so that <V—S> is not triple connected, which is a contradiction.

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 image, 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 image. Conversely, assume that image. Then the proof follows from proposition 3.1 to 3.6

Conclusion

In this paper, we characterized the 3- regular graphs for which image of order up to 10 vertices. The authors are also characterized 3-regular graphs for which image 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

  1. Harary, F. (1972). Graph theory. Addison Wesley Reading Mass.
  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.

Copyright © 2024 Research and Reviews, All Rights Reserved