SOME CHARACTERIZATION OF COMPLEMENTARY TRIPLE CONNECTED DOMINATION NUMBER OF 3 – REGULAR GRAPHS

Mahadevan G^1*, Iravithul Basira A² and Sivagnanam C³

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

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

³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

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⟩ ≠ K₃ ,K₂UK₁. Hence <V—S> = K₃ or P₃. Let <V— S> = K₃ or P₃. Then the possible case of <S> = K₃, P₃. 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₁, v₂, v₃, v₄, v₅}. <S> = K₃ or or K₁UK₂ or P₃ and, , K₅, W₅, F₂,, K₅-{e},, , C₃(P₃), C₃(2P₂), C₃(P₂,P₂,0) and the following (Fig. 2).

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

Case 1: Let < V—S> = C₅ = (v₁, v₂, v₃, v₄, v₅)

Since G is 3 - regular, it is clearly verified that <S> ≠ K₃ or or K₁∪K₂. Hence the only possible if <S> = P₃ = (x, y, z). Since G is connected 3 - regular, y must be adjacent to any one of the vertex of C₅. Let y be adjacent to v₁, since G is 3 - regular, x is adjacent to any two of { v₂, v₅} or v₂ (or v₅) and v₃(or v₄). Let x be adjacent to v₂ and v₅. Then z is must be adjacent to v₃ and v₄, so that . If x is adjacent to {v₂, v₃}, then z is must be adjacent to v₄ and v₅. In this stage {x, v₂} is - set, which is a contradiction. Hence no graph exists (Sivagnanam, 2012).

Case 2: < V—S> = P₅ = (v₁, v₂, v₃, v₄, v₅)

Since G is 3 - regular, it is clearly verified that <S>≠ K₃ or . Hence <S> = K₂∪K₁ or P₃.

Sub case (i) Let <S> = K₂∪K₁

Let xy be the edge in K₂∪K₁. Since G is connected let z be adjacent to both v₁ and v₅ and any one of {v₂, v₃, v₄} or z is adjacent to v₁(or v₅) and any two of {v₂, v₃, v₄} or z is adjacent to v₂ and v₃ and v₄. Let z is adjacent to v₁,v₅ and v₂. Then x is adjacent to v₁ and v₅ or x is adjacent to v₁ and v₃(or v₄) or x is adjacent to v₃ and v₄ or x is adjacent to v₅ and any one of {v₃, v₄}.

If x is adjacent to v₁ and v₅, then y must be adjacent to v₃ and v₄. In this stage {v₁, v₄} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v₁ and v₃ and then y must be adjacent to v₄ and v₅. In this stage {v₁, v₄} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v₃ and v₄, then y must be adjacent to v₅ and v₁. In this stage {v₁, v₄} be a - set, which is a contradiction. Hence no graph exists. If x is adjacent to v₅ and v₃, then y must be adjacent to v₄ and v₁ so that .

Let z be adjacent to v₁, v₂, v₃. Then x is adjacent to v₄ and v₅ or v₁ and v₄ or v₁ and v₅. If x is adjacent to v₄ and v₅, then y must be adjacent to v₁ and v₅. In this stage {v₅, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. If x is adjacent to v₁ and v₄, then y must be adjacent to v₅, since G is 3 - regular, which is a contradiction. If x is adjacent to v₁ and v₅, then y must be adjacent to v₄ and v₅. In this stage {y, z} be a ctc γ - set, which is a contradiction. Hence no graph exists. Let z be adjacent to v₂, v₃and v₄. Since G is 3 - regular, x be adjacent to v₁ and v₅, which is a contradiction.

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

Since G is 3 - regular, y is adjacent to v₁ (or v₅) or any one of {v₂, v₃, v₄}. If y is adjacent to v₁, since G is 3 - regular, x is cannot be v₁ and v₅ and also x cannot be adjacent to v₁ and any one {v₂, v₃, v₄} and x cannot be adjacent to any two of {v₂, v₃, v₄}, which is a contradiction. If y is adjacent to v₃, then x cannot be adjacent to v₁ and v₃, and also x cannot be adjacent to v₂ and v₃, 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₃ and P₃. Hence <S> = K₁∪K₂ or . Let <S₁> = N(x) = {v₁, v₂, v₃}. Let <S> = K₁∪K₂

Let yz be the edge in <S>. Let v₄ and v₅ be the vertices adjacent to y and v₆ and v₇ be adjacent to z. Let <S₂> = { v₄, v₅} and<S₃> = { v₆, v₇}. Then we will consider following three cases.

(i) <S₁> = P₃

<S₁> =

<S₁> = K₂∪K₁

Proposition: 3. 1

If <S> = K₁∪K₂ and <S₁> = P₃, then G is isomorphic to ς_j for 1 ≤ j ≤ 3 (Fig. 3).

Proof:

Let <S₁> = P₃ ={v₁, v₂, v₃}. We consider the following three cases.

Case1 <S₂> = <S₃> = K₂

Case2 <S₂> = K₂ and <S₃> =

Case3 <S₂> =<S₃> =

Case 1: <S₂> = <S₃> = K₂

Since G is 3 - regular, v₁ is adjacent to any one of { v₄, v₅, v₆, v₇}. Let v₁ be adjacent to v₄. Since G is 3 - regular, v₃ cannot be adjacent to v₅. Hence v₃ is adjacent to any one of { v₆, v₇}. Let v₃ be adjacent to v₆. Hence v₅ must be adjacent to v₇ so that G ≅ G₁

Case 2: <S₂> = K₂ and <S₃> =

If v₇ is adjacent to v₄ and v₅ or v₁ and v₃ or v₁ (or v₃) and v₄(or v₅). If v₇ is adjacent to v₄ and v₅, then v₆ is adjacent to v₁ and v₃ so that <V-S> is not triple connected, which is a contradiction. If v₇ is adjacent to v₁ and v₃, then v₆ is adjacent to v₄ and v₅ so that <V-S> is not triple connected, which is a contradiction. Hence v₇ is adjacent to v₁ and v₄, then v₆ is adjacent to v₃ and v₅ so that G ≅ G₂

Case 3: <S₂> =<S₃> = G ≅ G₃

Since G is 3 - regular, v₁ is adjacent to any one of { v₄, v₅, v₆, v₇}. Let v₁ is adjacent to v₄. Since G is 3 - regular, v₄ cannot be adjacent to v₃. Hence v₄ is adjacent to v₆(or v₇) and then v₇ is adjacent to v₃ and v₅ and since G is 3 - regular, v₅ is adjacent to v₆ so that G ≅ G₃

Proposition: 3.2

If <S> = K₁∪K₂ and <S₁> = ς_j, then G is isomorphic to ς_j for 4 ≤ j ≤ 7 (Fig. 4).

Proof: We consider the following three cases.

Case 1: <S₂> = <S₃> = K₂

<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₂> = K₂ and <S₃> =

v₁ is adjacent to v₄ and v₅ (or) v₆ and v₇ (or) v₄ (or v₅) and v₆(or v₇). If v₁ is adjacent to v₄ and v₅, then v₂ is adjacent to v₆ and v₇ and then v₃ is adjacent to v₆ and v₇. In this stage if we take S = { v₄, v₂, v₇} with v₂v₇ ЄE(G), then S is a dominating set. Let S₁= {v₅, y, v₁}. Now, in this situation <S> = K₁∪K₂, <S₁> = P₃ which falls under proposition:3.1

If v₁ is adjacent to v₆ and v₇, then v₂ is adjacent to v₄ and v₅,(or) v₆ and v₇ (or) v₄(or v₅) and v₆(or v₇). If v₂ is adjacent to v₄ andv₅, then v₃ is adjacent to v₆ and v₇. In this stage if we take S = { v₅,v₁,v₆} with v₁v₆ ЄE(G), then S is a dominating set. Let S₁= {y, v₄, v₂}. Now, in this situation <S> = K₁∪K₂, <S₁> = P₃ which falls under proposition:2.1. If v₂ is adjacent to v₄ andv₆, then v₃ is adjacent to v₇ and v₅ so that G ≅ G₄.

v₁ is adjacent to v₄ and v₆. Since G is 3 - regular, v₂ is not adjacent to v₅ and v₆ and hence it must be adjacent to v₅ and v₇(or) v₆ and v₇. If v₂ is adjacent to v₅ and v₇, then v₃ is adjacent to v₆ and v₇ so that G ≅ G₄.

Case 3: <S₂> =<S₃> =

Now v₁ is adjacent to v₄ and v₅(or v₆ and v₇) or v₄ and v₆. If v₁ is adjacent to v₄ and v₅, then since G is 3 - regular, v₂ is not adjacent to v₄ and v₅. Hence v₂ is adjacent to v₆ and v₇ or v₄ (or v₃) and v₆(or v₇).

If v₂ is adjacent to v₆ and v₇, then v₃ is not adjacent to v₄ and v₇. Also v₃ is not adjacent v₆ and v₇. Hence v₃ is adjacent to v₄(or v₅) and v₆ (or v₇) and then v₇ is adjacent to v₅ so that G ≅ G₅. If v₂ is adjacent v₄ and v₆, then v₇ is adjacent to v₅ and v₃ and then v₃ is adjacent to v₆ so that G ≅ G₆.

If v₁ is adjacent to v₆ and v₄, then v₂ is adjacent to v₆ and v₄ or v₇ and v₅ or v₆ and v₇(or v₄ and v₅) or v₆ and v₇ (or v₇ and v₄). If v₂ is adjacent to v₆ and v₄,then v₃ is adjacent v₇ and v₅ and then v₅ is adjacent to v₇ so that <V-S> is not triple connected, which is a contradiction.

If v₂ is adjacent to v₇ and v₅, then v₃ cannot be adjacent to v₄ and v₇ (or v₆ and v₇). Hence v₃ is adjacent to v₄ and v₆ or v₅ and v₇ or v₄ and v₇ (or v₆ and v₇).

If v₃ is adjacent is adjacent to v₄ and v₆, then v₇ is adjacent to v₅ so that <V-S> is not triple connected. If v₃ is adjacent to v₅ and v₇, then v₆ is adjacent to v₄ so that <V-S> is not triple connected. If v₃ is adjacent to v₇ and v₄, then v₆ is adjacent to v₅ so that G ≅ G₆.

If v₂ is adjacent to v₆ and v₅, then v₃ cannot be adjacent to v₄ and v₅. Hence v₃ is adjacent to v₄ and v₇ or v₇ and v₅. If v₃ is adjacent to v₇ and v₄, then v₇ is adjacent to v₅ so that G ≅ G₇. If v₃ is adjacent to v₅ and v₇, then v₇ is adjacent to v₄ so that G ≅ G₇.

If v₂ is adjacent to v₆ and v₇, then v₃ cannot be adjacent to v₇ and v₄. Also v₃ is not adjacent to v₇ and v₅. Hence v₃ is adjacent to v₄ and v₅ and then v₅ is adjacent to v₇ so that G ≅ G₅.

Proposition: 3.3

If <S> = K₁∪K₂ and <S₁> = K₂∪K₁, then G is isomorphic to ς_j for 8 ≤ j ≤ 11 (Fig. 5).

Proof: Let v₁ v₂ be the edge in <S₁>. We consider the following three cases.

Case 1: <S₂> = <S₃> = K₂

Now, v₃ is adjacent to v₄ and v₅ (or v₆ and v₇) or v₆ and v₄ (or v₇ and v₅). If v₃ is adjacent to v₄ and v₅, then v₂ is adjacent t to v₆ (or v₇) and then v₁ is adjacent to v₇. In this stage, if we take S = { v₄, v₂,v₆} with v₂v₆ ε E(G), then S is a dominating set. Let S₁ = (v₅,y,v₃}. Now in this situation <S>=K₁∪K₂, <S₁>= P₃ which follows under proposition 3.1 If v₃ is adjacent to v₆ and v₄, then v₁ is adjacent v₇ (or v₅) and then v₂ is adjacent to v₅ so that G ≅ G₈.

Case 2: <S₂> = K₂ and <S₃> =

Since G is 3 - regular, v₃ cannot be adjacent to v₄ and v₅. Hence v₃ is adjacent to v₆ ( or v₇) and v₄(or v₅) and v₆ (or v₅). If v₃ is adjacent to v₆ and v₇, then v₆ is adjacent to v₁(or v₂) or v₄( or v₅). If v₆ is adjacent to v₁, then v₇ is not adjacent to v₂ and hence v₇ is adjacent to v₄(or v₅) and then v₅ is adjacent to v₂ so that G ≅ G₉.

If v₆ is adjacent to v₄, then v₇ is not adjacent to v₅. Hence v₇ is adjacent to v₁(or v₂) and then v₂ is adjacent to v₅ so that G ≅ G₉. If v₃ is adjacent to v₄ and v₆, then v₇ is adjacent to v₁ and v₂ or v₁(or v₂) and v₅. If v₇ is adjacent to v₁ and v₂, then v₆ is adjacent to v₅. In this stage, if we take S = { v₅, v₆,v₁} with v₅v₆ ε E(G), then S is a dominating set. Let S₁ = (x,v₂,v₇}. Now in this situation <S> = K₁ ∪ K₂, <S₁> = P₃ which follows under proposition 3.1. If v₇ is adjacent to v₁ and v₅, then v₂ is adjacent to v₆ so that G ≅ G₁₀.

Case 3: <S₂> =<S₃> =

Now v₃ is adjacent to v₆ and v₇(or v₄ and v₅) or v₆ and v₄(or v₇ and v₅). If v₃ is adjacent to v₆ and v₇. In this stage, if we take S = {x, v₃,y} with xv₃ ε E(G), then S is a dominating set. Let S₁ = (z,v₄,v₅}. Now in this situation <S> = K₁∪K₂, <S₁> = G ≅ G₁₁ which follows under proposition 3.2. If v₃ is adjacent to v₆ and v₄, then v₇ is not adjacent to v₁ and v₂. Hence v₇ is adjacent to v₄ and v₅ or v₁ and v₄ or v₁ and v₅.

If v₇ is adjacent to v₄ and v₅, then v₅ is not adjacent to v₆. Hence v₅ is adjacent to v₁(or v₂) and then v₂ is adjacent to v₆. In this stage, if we take S = {v₃,v₆,v₅} with v₃v₆ Є E(G), then S is a dominating set. Let S₁ = (y,v₇,v₁}. Now in this situation <S> = K₁∪K₂, <S₁> = G ≅ G₁₁ which follows under proposition 3.2. If v₇ is adjacent to v₁ and v₄, then v₅ is adjacent to v₂ and v₆ so that G ≅ G₁₁.

If v₇ is adjacent to v₁ and v₅, then v₂ is not adjacent to v₆. Hence v₂ is adjacent to v₄ and v₅. If v₂ is adjacent to v₄, then v₅ is adjacent to v₆. In this stage, if we take S = {v₇,v₁,v₄} with v₇v₁ Є E(G), then S is a dominating set. Let S₁ = (y,v₃,v₆}, S₂ = (v₅,z}, S₃ = (v₂,x}. Now in this situation <S> = K₁∪K₂, <S₁> = K₂∪K₁, <S₂> = and <S₃> = K₂ 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₄ and v₅. Let S₂ = {v₄,v₅}. Then z is adjacent to two vertices say v₆ and v₇. Let S₃ = {v₆,v₇}. Then we will consider the following three situations.

(i) <S₁> = P₃

(ii) <S> = K₂∪K₁

<S₁> =

Proposition 3. 4

If <S> = and <S₁> = P₃, then no new graph exists.

Proof: Let <S₁> = P₃ = (v₁v₂v₃). We consider the following 3 cases.

Case 1: <S₂> = <S₃> = K₂

Let U = S₂∪{y} and V = S₃∪{z}. Then <U> = <V> = C₃. 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₁∪K₂, which falls under propositions <S> = K₁∪K₂.

Case 2: <S₂> = K₂ and <S₃> =

Let v₄ and v₅ be the edge in S₂. Since G is 3 - regular y cannot be adjacent to v₁(or v₃). Hence y is adjacent to v₆ (or v₇). If y is adjacent to v₆(or v₇), then v₇ is adjacent v₁ and v₃ or v₅ and v₄ or v₄(or v₅) and v₁(or v₃). If v₇ is adjacent to v₁ and v₃, then v₆ is adjacent to v₄(or v₅) and then z is adjacent to v₅. In this situation if we take S = {x,v₅,z} with v₅z Є E(G) then S is a dominating set. Let S₁ = {v₁,v₂,v₃}. Now in this situation <S> = K₁ K₂, <S₁> = P₃ which falls under proposition 3.1. If v₇ is adjacent v₁ and v₄, then v₅ is not adjacent v₃. Hence v₅ is adjacent to v₆ or z. If v₅ is adjacent to v₆, then z is adjacent to v₃ so that <V S> is not triple connected, which is a contradiction. If v₅ is adjacent to z, then v₃ is adjacent to v₆. In this stage, if we take S = { x, v₅,z} with v₅z Є E(G), then S is a dominating set. Let S₁ = (v₁,v₂,v₃}. Now in this situation <S> = K₁∪K₂, <S₁> = P₃ which follows under proposition 3.1. If v₇ is adjacent to v₅ and v₄, then v₆ is adjacent to v₁(or v₃) and z is adjacent to v₃ so that <V—S> is not triple connected, which is a contradiction.

Case 3: <S₂> =<S₃> =

Now y is adjacent to v₁(or v₃) or v₆(or v₇). In both cases no new graph exists.

Proposition 3. 5

If <S> = ς_j and <S₁> = K₂∪yK₁, then G is isomorphic to ς_j for 11 ≤ j ≤ 13 (Fig. 6).

Proof: Let v₁v₂ be the edge in <S₁>. We considers the following three cases.

Case 1: <S₂> = <S₃> = K₂

Now v₁ is adjacent to any one of {v₄,v₅,y}(or any one of{v₆,v₇,w}). Let v₁ is adjacent to v₄. Then no new graph exists.

Case 2: <S₂> = K₂ and <S₃> =

Now v₁ is adjacent to any one of {y,v₄,v₅} or z or v₆ (or v₇). If v₁ is adjacent to y, then z is adjacent to v₃ or v₄(or v₅) or v₂. Let z is adjacent to v₃. In this stage, if we take S = { z,v₁,y} with v₁y E(G), then S is a dominating set. Let S₁ = (v₃,v₆,v₇}. Now in this situation <S> = K₁∪K₂, <S₁> = which follows under proposition 3.2. If z is adjacent to v₄. In this stage, if we take S = { x,v₄,z} with v₄z Є E(G), then S is a dominating set. Let S₁ = (v₁,v₂,v₃}. Now in this situation <S> = K₁∪K₂, <S₁> = K₁∪K₂ which follows under proposition: 3.3. If z is adjacent to v₂, then v₅ is adjacent to v₃ or v₆(or v₇). Let v₅ is adjacent to v₃. In this stage, if we take S = { v₅,v₂,z} with v₂z Є E(G), then S is a dominating set. Let S₁ = (v₃,v₄,y}. Now in this situation <S> = K₁∪K₂, <S₁> = K₁∪K₂ which follows under proposition 3.3. If v₅ is adjacent to v₆, then v₇ is adjacent to v₃ and v₄, and then v₃ is adjacent to v₆ so that G ≅ G₁₂. If v₁ is adjacent to z, then no new graph exists. If v₁ is adjacent to v₆, then v₆ is adjacent to any one of{y,v₄,v₅} or v₃ or v₂. If v₆ is adjacent to y, then z is adjacent to v₃ or v₂ or v₄ (or v₅). If z is adjacent to v₃, then v₂ is adjacent to v₄ (or v₅) or v₇. If v₂ is adjacent to v₄, then v₇ is adjacent to v₃ and v₅. In this stage, if we take S = { y,v₃,x} with v₃x Є E(G), then S is a dominating set. Let S₁ = (v₄,v₅,v₆}. Now in this situation <S> = K₁∪K₂, <S₁> = K₁∪K₂ which follows under proposition 3.3. If v₂ is adjacent to v₇, then since G is 3 - regular v₇ cannot be adjacent to v₃. Hence v₇ must be adjacent to v₄ (or v₅) and then v₃ is adjacent to v₅ so that G ≅ G₁₃. If z is adjacent to v₂ or v₄, then no new graph exists. If v₆ is adjacent to v₃ or v₂, then no new graph exists.

Case 3: <S₂> =<S₃> =

Now v₁ be adjacent to y(or z) or v₄(or v₅){or v₆(or v₇)}. In both cases no new graph exists.

Proposition: 3.6

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

Proof: We consider the following three cases.

Case 1: <S₂> = <S₃> = K₂

Let v₄ v₅ be the edge in <S₂> and v₆v₇ be the edge in <S₃>. Now v₁ is adjacent to any two of {y,v₄,v₅} (or equivalently { z,v₆,v₇}) or any one of {y,v₄,v₅} and any one of{z,v₆,v₇}. In both cases no new graph exists.

Case 2: <S₂> = K₂ and <S₃> =

Now z is adjacent to any one of {v₁,v₂,v₃}. Let z be adjacent to v₁. Then y is adjacent to v₁ or not adjacent to v₁. In both cases no new graph exists.

Case 3: <S₂> =<S₃> =

Now v₁ is adjacent to v₄ ( or v₅) or v₁ is adjacent to y (or z). If v₁ is adjacent to v₄, then y is adjacent to v₁ or v₂ (or v₇). If y is adjacent to v₁. In this stage, if we take S = { y,x,z}, then S is a dominating set. Let S₁ = (v₁,v₄,v₅}. Now in this situation <S> = , ,<S> = K₁∪K₂ which follows under proposition 3.5. If y is adjacent to v₂, then z is adjacent to v₂ or v₁(or v₄) or v₃ (or v₅). If z is adjacent v₂, then v₆ is adjacent to v₃ and v₅ or v₁ and v₄ or v₃ (or v₅) and v₁( or v₄). If v₆ is adjacent to v₃ and v₅, then v₄ is adjacent to v₃ or v₇. If v₄ is adjacent to v₃, then v₇ is adjacent to v₁ and v₅ so that <V—S> is not triple connected, which is a contradiction.

If v₄ is adjacent to v₇, then v₁ is adjacent to v₅ or v₇, then v₁ is adjacent to v₅ or v₇. If v₁ is adjacent to v₅, then v₃ is adjacent to v₇ so that<V—S> is not triple connected, which is a contradiction. If v₁ is adjacent to v₇, then v₃ is adjacent to v₅. In this stage, if we take S = { v₃,v₂,v₄}, then S is a dominating set. Let S₁ = (x,v₅,v₆}. Now in this situation <S> = , <S₁> = K₁∪K₂ which follows under proposition 3.5. If v₆ is adjacent to v₁ and v₄, then v₅ is adjacent to v₃ and v₇ and then v₃ is adjacent to v₇. In this stage, if we take S = { v₂,v₄,v₃}, then S is a dominating set. Let S₁ = (y,v₁,v₆}. Now in this situation <S> = , <S₁> = K₁∪K₂ which follows under proposition 3.5. If v₆ is adjacent to v₃ and v₁, then v₅ is adjacent to v₃ and v₇, and then v₇ is adjacent to v₄ so that <V—S> is not triple connected, which is a contradiction. If z is adjacent to v₁ or v₃, then no new graph exists. If y is adjacent to v₆, then z is adjacent to v₁ or v₄ or v₅ or v₂(or v₃). If z is adjacent to v₁, then no new graph exists. If z is adjacent to v₄, then v₆ is adjacent to v₁ or v₂(or v₃). If v₆ is adjacent to v₁, then v₂ is adjacent to v₅ and v₇ and then v₃ is adjacent to v₅ and v₇ so that <V—S> is not triple connected, which is a contradiction.

If v₆ is adjacent to v₂, then v₁ is adjacent to v₅ or v₇. If v₁ is adjacent to v₅, then v₃ is adjacent to v₅ and v₇, and then v₂ is adjacent to v₇ so that G ≅ G₁₄. If v₁ is adjacent to v₇, then v₃ is adjacent to v₅ and v₇, and then v₂ is adjacent to v₅ so that G ≅ G₁₄. If z is adjacent to v₅ or v₂, then no new graph exists. If v₁ 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

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.