Printer Friendly

Weakly convex domination in graphs.

[section]1. Introduction and preliminaries

A dominating set D is said to be a connected dominating set if for every u, v [member of] D, there exists an u - v path in (D).

The cardinality of a minimum connected dominating set is called the connected domination number of G and is denoted by [gamma]c(G).

A dominating set D is said to be a weakly convex dominating set (wcd set) if for every u, v [member of] D, either u and v are not connected or there exists a u - v shortest path (of G), in <D>.

The cardinality of a minimum wcd set is called the weakly convex domination number of G and is denoted by [[gamma].sub.wc](G).

[gamma](G) [less than or equal to] [[gamma].sub.c](G) [less than or equal to] [[gamma].sub.wc](G). In this paper, graphs with [gamma](G) = [[gamma].sub.wc](G) and [[gamma].sub.c](G) = [[gamma].sub.wc](G) are characterized.

[section]2. Weakly convex domination in graphs

A dominating set D is said to be a weakly convex dominating set (wcd set) if for every u, v [member of] D, either u and v are not connected or there exists a u - v shortest path (of G), in <D>.

The cardinality of a minimum wcd set is called the weakly convex domination number of G and is denoted by [[gamma].sub.wc](G).

Observation. For any graph G,

(i) [[gamma].sub.t(G)] [less than or equal to] [[gamma].sub.wc](G), where [[gamma].sub.t](G) is the total domination number of G.

(ii) [gamma](G) [less than or equal to] [[gamma].sub.c](G) [less than or equal to] [[gamma].sub.wc](G), where [gamma](G) is the domination number and [[gamma].sub.c](G) is the connected domination number of G.

Example.

(i) [[gamma].sub.wc]([P.sub.2]) = 1.

(ii) [[gamma].sub.wc]([P.sub.n]) = n - 2 for any positive integer integer n [greater than or equal to] 3.

(iii) [[gamma].sub.wc]([K.sub.n]) = 1 for any positive integer n.

(v) [[gamma].sub.wc]([K.sub.m,n]) = 2 for any positive integer m and n.

(vi) [[gamma].sub.wc]([W.sub.n]) = 1 for any positive integer n.

Notion. The length of a smallest cycle in G is called the girth of G and is denoted by g(G).

Lemma. If G is a graph with [delta](G) [greater than or equal to] 2 and g(G) [greater than or equal to] 7 then [[gamma].sub.wc](G) = n.

Proof. Let if possible there exist a proper wcd set D. Then V - D [not equal to] [PHI]. Then for every u [member of] V - D there exists [u.sub.i] [member of] D such that u[u.sub.i] [member of] E(G). [delta](G) [greater than or equal to] 2 implies there exists ([u.sub.2])([not equal to] [u.sub.1]) [member of] N(u). Therefore, d([u.sub.1], [u.sub.2]) [less than or equal to] 2.

If [u.sub.2] [member of] D, then [u.sub.1], [u.sub.2] [member of] D implies there exists [u.sub.1]...[u.sub.2] shortest path in D. This shortest path (or geodesic) must have length at most two whence it follows that G has a cycle [C.sub.n] for n [member of] {3,4}, a contradiction to our hypothesis that g(G) [greater than or equal to] 7. Therefore, [u.sub.2] [not member of] D and hence [u.sub.2] [member of] V - D.

Then N([u.sub.2]) [intersection] D [not equal to] [PH]. Therefore [u.sub.2] may be adjacent to [u.sub.1] or there exists [u.sub.3]([not equal to [u.sub.1]) [member of] D such that [u.sub.3][u.sub.2] [member of] E(G).

If [u.sub.2][u.sub.1][member of] E(G) then there will exist a 3 cycle.

If there exists [u.sub.3]([not equal to] [u.sub.1]) [member of] D such that [u.sub.3][u.sub.2] [member of] E(G), then d([u.sub.1], [u.sub.3]) < 3. [u.sub.1], [u.sub.3] [member of] D implies there exists an [u.sub.1]...[u.sub.3] shortest path in <D>.

If d([u.sub.1], [u.sub.3)] = 1 then there will exist a 4 cycle.

If d([u.sub.1], [u.sub.3)] = 2 then there will exist a 5 cycle.

If d([u.sub.1], [u.sub.3)] = 3 then there will exist a 6 cycle.

...

A contradiction. (since g( G) > 7) and therefore G cannot have a proper wcd set. (i.e.) [[gamma].sub.wc](G) = n.

Corollary. If [[gamma].sub.wc](G) < n then either 5 < 1 (or) g(G) < 6.

Remark. From Lemma 1 we can conclude that there exist infinitely many number of graphs G with [[gamma].sub.wc](G) = n.

Observation. [7.sub.wc]([C.sub.n]) = n - 2 for any integer 3 [less than or equal to] n [less than or equal to] 6 and is equal to n for n [greater than or equal to] 7.

Proof. (i) If 3 [less than or equal to] n [less than or equal to] 6, then choose any u, v [member of] V([C.sub.n]) with uv [member of] E(G) and consider D = V([C.sub.n]) - {u,v}. Then D is a dominating set of [C.sub.n]. For any x,y [member of] D, if there exists no x...y shortest path in <D>, then [d.sub.<D>](x,y) > d(x,u) + d(u,v) + d(v,y) [greater than or equal to] 3. Therefore [d.sub.<D>] (x,y) [greater than or equal to] 3. (ie) [d.sub.<D>](x,y) [greater than or equal to] 4.

[ILLUSTRATION OMITTED]

Then x..yvu..x is a cycle of length atleast 7, a contradiction. Hence, for any two x,y [member of] D there exists an x...y shortest path in D. (i.e.) D is a wcd set. Therefore [[gamma].sub.wc]([C.sub.n])) < n - 2. 7c(C") = n - eT(G) where eT(G) is the maximum number of pendant vertices in any spanning tree TG of G. (i.e.) n - 2 = Yc([C.sub.n]) < [[gamma].sub.wc]([C.sub.n]) [less than or equal to] n - 2. Hence [[gamma].sub.wc]([C.sub.n]) = n - 2 for n, 3 [less than or equal to] n [less than or equal to] 6.

(ii) If n [greater than or equal to] 7, by Lemma 1 we can conclude that [[gamma].sub.wc]([C.sub.n]) = n.

Remark. From the above observation we can conclude that the following disconnected graph has no proper wcd set.

[FIGURE 3(a) OMITTED]

Remark. If G is a disconnected graph and [D.sub.1] is a proper wcd of a component [C.sub.1] of G, then (V(G) - V([C.sub.1])) [union] [D.sub.1] is a proper wcd set of G. And if no component of G has a proper wcd set, then G cannot have a proper wcd set. (i.e.) A disconnected graph G has a proper wcd set if and only if there exists a component C1 of G with proper wcd set. Hence wcd sets in a disconnected graph can be analysed by studying the wcd sets of it's components. For this purpose first we make a complete study of wcd sets in connected graphs. In the following discussion by a graph we always mean a connected graph.

Remark. From the Lemma 1 we can conclude that 1 [less than or equal to] [[gamma].sub.wc](G) < n.

Remark. [[gamma].sub.wc](G) = 1 if and only if G has a vertex of full degree.

Remark. Every graph with diam(G) [less than or equal to] 2 has a proper wcd set.

Proof. If diam(G) = 1 with n [greater than or equal to] 2 then G is [K.sub.n]. Therefore D = {u} is a wcd set for any u [member of] V(G). If diam(G) = 2 then for any u [member of] V(G) with degu = A, N[u] is a wcd set. For if x,y [member of] N[u] either xy [member of] E(G) (or) <x,u,y> is connected. Therefore N[u] is weakly convex. Let v [member of] V - N[u]. Then v must be adjacent to atleast one [v.sub.1] G N(u). For otherwise d(u,v) [greater than or equal to] 3. Hence for every v [member of] V - N[u] there exists [v.sub.1] [member of] N(u) such that v[v.sub.1] [member of] E(G). Therefore N[u] is a dominating set.

Remark. All graphs (with diam(G) > 2) need not have a proper wcd set.

Example. [C.sub.n] with n [greater than or equal to] 7 has no proper wcd set.

Observation. For any tree T of order n, [[gamma].sub.wc](T) = n - [epsilon] where [epsilon] denotes the number of pendant vertices of the given tree T.

Proof. D = V(T) - A, where A is the set of all pendant vertices of T, is a wcd set of T. Hence [[gamma].sub.wc](T) [less than or equal to] n - [epsilon]. Therefore n - [epsilon] = [[gamma].sub.c](T) [less than or equal to] [[gamma].sub.wc](T) [less than or equal to] n - [epsilon]. (i.e.) [[gamma].sub.wc](T) = n - [epsilon].

Remark. [[gamma].sub.wc](T) = n - 2 if and only if T is a path.

Proof. Let [[gamma].sub.wc](T) = n - 2 for a tree.

Claim. T is a path. (i.e.) To prove that T has exactly two pendant vertices.

Let A be the set of all pendant vertices of T. Then D = V(T) - A is a wcd set and hence [[gamma].sub.wc](T) [less than or equal to] n - [absolute value of A] [less than or equal to] n - 2 (since [absolute value of A] [greater than or equal to] 2 for any non trivial tree). If [absolute value of A] [greater than or equal to] 2 then n - 2 = [[gamma].sub.wc](T) [less than or equal to] n - [absolute value of A] [less than or equal to] n - 2 ... a contradiction. Hence T is a tree with exactly two pendant vertices. (i.e.) T is a path.

Conversely, if T is a path then [[gamma].sub.wc](T) = n - 2.

Notation. [[epsilon].sub.T](G) denote the number of pendant vertices of a spanning tree [T.sub.G] (of a connected graph) G with maximum number of pendant edges.

Observation. If G is a unicyclic graph then [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) (or) n - [[epsilon].sub.T](G) + 1 (or) n - [[epsilon].sub.T](G) + 2.

Proof. If A is the set of all pendant vertices of a spanning tree [T.sub.G] of G with maximum number of pendant edges, then [absolute value of A] = [[epsilon].sub.T](G). Let [C.sub.r] be the unique cycle of G where r denote the length of the cycle [C.sub.r]. Let B = {u [member of] V([C.sub.r])/N(u) [intersetion] (V(G) - V([C.sub.r])) = [PHI]}.

case(i): B = [phi].

In this case for any r [greater than or equal to] 3, N(u) [intersection] (V(G) - V([C.sub.r])) [not equal to] [PHI] for each u [member of] V([C.sub.r]). Then A [intersection] B = [PHI] and D = V(G) - A is a wcd set. Therefore [[gamma].sub.wc](G) < n - [[epsilon].sub.T](G). Hence n - [[epsilon].sub.T](G) = [[gamma].sub.c](G) [less than or equal to] [[gamma].sub.wc](G) [less than or equal to] n - [[epsilon].sub.T](G). (i.e.) [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G).

Case(ii): B [not equal to] [PHI] and B is independent.

(a) r = 3

B is an independent subset of a 3 cycle implies [absolute value of B] = 1. Let B = {x} where x [member of] V([C.sub.3]) = {x,y,z}. In this case G can be obtained by taking a [C.sub.3] : xyzx and attaching one or more nontrivial trees at two vertices y and z.

Therefore N(y) [intersection] (V(G) - V([C.sub.3])) [not equal to] [PHI], N(z) [intersection] (V(G) - V([C.sub.3]) = [PHI] and [FIGURE 4 OMITTED]

N(x) [intersection] (V(G) - V([C.sub.3])) = [PHI]. (i.e.) x is a pendant vertex in any spanning tree of G. Therefore x [member of] A, and D = V(G) - A is a wcd set. Therefore [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) as in case (i).

(b) r = 4

B is an independent subset of a 4 cycle implies [absolute value of B] [less than or equal to] 2.

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

If [absolute value of B] where x [member of] V([C.sub.4]) = {x,y,z,w}. In this case G can be obtained by taking a 4 cycle [C.sub.4] : xyzwx and attaching one or more nontrivial trees at three consecutive vertices y, z,w. Then as in case (i) [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G).

If [absolute value of B] = 2, then let B = {x,z}. In this case G can be obtained by taking a 4 cycle [C.sub.4] : xyzwx and attaching one or more nontrivial trees at two non consecutive vertices y and w. Then either x (or) z is in A. Both x and z cannot be in A. Since the possible spanning trees are:

[FIGURE 7 OMITTED]

[FIGURE 8 OMITTED]

Again as in case (i) [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G). (c) r = 5

[ILLUSTRATION OMITTED]

B is an independent subset of a 5 cycle implies [absolute value of B] [less than or equal to] 2.

If [absolute value of B] = 1 let B = {x} where x [member of] V([C.sub.5]) = {x,y,z,v,w}. In this case G can be obtained by taking a 5 cycle [C.sub.5] : xyzvwx and attaching one or more nontrivial trees at four consecutive vertices y,z,v, and w. N(x) [intersection] (V(G) - V([C.sub.5])) = [PHI]. (i.e.) x is a pendant vertex in any spanning tree of G and therefore x [member of] A. But D = V(G) - A is not a wcd set. (since [d.sub.<D>](y,w) = 3 > [d.sub.G] (y,w) = 2). But D' = (V(G) - A) [union] {x} is a wcd set. Hence [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) + 1.

If [absolute value of B] = 2, let B = {x, v}. In this case G can be obtained by taking [C.sub.5] : xyzvwx and attaching one or more nontrivial trees at y, z, w. Then either x or v is in A. Both x and v cannot be in A. If x e A, then [d.sub.<D>](w,y) = 3 > [d.sub.G](w,y) = 2 and hence D = V(G) - A is not a wcd set. But D' = (V(G) - A) [union] {x} is a wcd set. Similarly D' = (V(G) - A) [union] {y} is a wcd set. Therefore [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) + 1.

(d) r = 6

B is an independent subset of a 6 cycle implies [absolute value B] [less than or equal to] 3.

[ILLUSTRATION OMITTED]

Then the possible independent sets are: {x}, {x,w} and {x,z,v}. Arguing as in the previous case we get

[[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) + 1

(e) r [greater than or equal to] 7

B is independent subset of [C.sub.r] with r [greater than or equal to] 7 implies [absolute value of B] = [r/2] and [absolute A [intersection] B] = 1. If x [member of] [absolute value of A [intersection] B] and [x.sub.1],[x.sub.2] [member of] N(x) [intersection] V([C.sub.r]). r [greater than or equal to] 7 implies there exists no [x.sub.1]...[x.sub.2] shortest path in V(G) - {x}. Therefore D = V(G) - A is not a wcd set. But D' = (V(G) - A) [union] {x} is a wcd set. Hence [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) + 1.

Case(iii): B is not independent.

Then there exists u, v [member of] B with uv [member of] E([C.sub.r]). Therefore N(u) [intersection] (V(G) - V([C.sub.r])) = [PHI] and N(v) [intersection] (V(G) - V([C.sub.r])) = [PHI]. Therefore u, v are pendant vertices in any spanning tree of G. (i.e.) u, v [member of] A.

(iii) - (a): 3 [less than or equal to] r [less than or equal to] 6.

[ILLUSTRATION OMITTED]

Then D = V(G) - A is a wcd set of G and hence [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G). (iii) - (b): r > 7.

[ILLUSTRATION OMITTED]

Then D = V(G) - A is not a wcd set. (since [d.sub.<D>]([u.sub.l],[v.sub.l]) = 4 > [d.sub.G]([u.sub.l],[v.sub.l]) = 3 where [u.sub.1] [member of] N(u) and [v.sub.l] [member of] N(v)). But D' = (V(G) - A) [union] {u,v} is a wcd set. Therefore [[gamma].sub.wc](G) = n - [[epsilon].sub.T](G) + 2.

If G is a graph with [delta](G) = 1, then D = V(G) - {u} where deg u = [delta] is a wcd set of G (i.e). G has a proper wcd set.

Lemma. If B is a block of a separable graph G with wcd set B' containing all cut vertices belonging to B then (V - B) [union] B' is a wcd set of G.

Proof. Let D = (V - B) [union] B'. Then for each u [member of] V - D = V -[(V - B) [union] B'] = B - B' there exists v [member of] B' such that uv [member of] E(G) (since B' is a wcd set of B). Therefore D is a dominating set of G.

Let x,y [member of] (V - B) [union] B'.

Case I: Every block of G is incident at the same cut vertex. (i.e.) G has exactly one cut vertex, say w. As B' contains all cut vertices belonging to B, w [member of] B'.

I - (a): x, y e V - B.

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

I - (a): x, y [member of] V - B.

First, we observe that every x - y shortest path (of G) in <(V - B) [union] {w}) has no vertex from B - {w} and it may or may not contain w. (i.e.) there exists an x - y shortest path (of G) in <(V - B) [union] {w}) not containing w or containing w. If this x - y shortest path does not contain w then this path completely lies in <V - B>. If it conains w then this path is contained in <(V - B) U B'>.

I - (b): x [member of] V - B and y [member of} B'.

Then the x - w shortest path of G in ((V - B) U {w}) together with the w - y shortest path in B' gives an x - y shortest path of G in <(V - B) U B'>.

Case II: G has at least two cut vertices.

II - (a): If B is an end block then B has exactly one cut vertex, say w. Then arguing as in the previous case we get the result.

[ILLUSTRATION OMITTED]

II - (b): If B is not an end block then B may have more than one cut vertex. Let {[w.sub.1], [w.sub.2],...,[w.sub.r]} be the set of cut vertices belonging to B. Then {[w.sub.1], [w.sub.2],...,[w.sub.r]} [subset or equal to] B'. As B' is a wcd set of B there exists a shortest path connecting any two cut vertices [w.sub.i] and [w.sub.j] in <B'>. Again, for any two x,y [member of] (V - B), every x - y shortest path (of G) in <(V - B) [union] {[w.sub.i], [w.sub.2],...,[w.sub.r]}> has no vertex from B - {[w.sub.1], [w.sub.2],..., [w.sub.r]} and it may or may not contain some or all of [w.sub.1], [w.sub.2],...,[w.sub.r]. (i.e.) there exists an x - y shortest path (of G) in V - B not containing any of the cut vertices [w.sub.1], [w.sub.2],...,[w.sub.r] or containing some or all of [w.sub.1], [w.sub.2 ,...,[w.sub.r].

II - (b) - (i): x,y [member of] (V - B).

If the x - y shortest path has no [w.sub.i] then the x - y shortest path completely lies in <V - B>. If it contain some or all of [w.sub.i] then the x - y shortest path lies in <(V - B) U B'>.

II - (b) - (ii): x [member of] (V - B) and y [member of] B'.

Then there exists an x - [w.sub.i] shortest path in <(V - B) [union] {[w.sub.i]}) for every i. [w.sub.i],y [member of] B' implies there exists an wi - y shortest path in (B'). Hence x - wi - y is an x - y shortest path in <(V - B) [union] B'>.

In both cases I and II, if x, y [member of] B' then as B' is a wcd set of B there exists an x - y shortest path (of B) which is also an x - y shortest path of G is in B'.

Hence in all cases (V - B) [union] B' is a wcd set of G.

Notation. The length of a longest cycle in G is called the circumference of G and is denoted by c(G).

Definition. In a separable graph G, a block with at most one cut vertex is called an end block.

lemma. If G is a block with 3 [less than or equal to] c(G) [less than or equal to] 6, then [[gamma].sub.wc](G) < n.

Proof. Case (i): c(G) = 3.

Let [C.sub.r] be a cycle with r = 3. If G = [C.sub.r], then obviously [[gamma].sub.wc](G) < n. If G [not equal to] [C.sub.r] then there exists an edge uv [member of] E(G) such that u [member of] V([C.sub.r]) and v [member of] V(G) - V([C.sub.r]). Take any other u' [member of] V([C.sub.r]). Then uv is an edge and u' is another vertex and G is a block implies there exists a cycle containing uv and u'. But if there exists a cycle containing uvu' then c(G) > 3 which is not true. Therefore there cannot exist v [member of] V(G) - V(Cr). (i.e.) G = C3 and D = {u} is a wcd set. Hence [[gamma].sub.wc](G) = 1 < n.

Case (ii): c(G) = 4.

G is a block with c(G) = 4 implies diam(G) [less than or equal to] 2. If diam(G) = 1, then D = {u} is a wcd set of G for any u [member of] V(G). If diam(G) = 2, then for any u [member of] V(G), D = N[u] is a wcd set. For if, v [member of] V(G) - N[u] then v cannot be adjacent to u. Therefore v must be adjacent to some [v.sub.i] N(u). (otherwise d(v,u) > 2). (i.e.) D is a dominating set. For any x,y [member of] N[u] there exists x...y shortest path in N[u]. (i.e.) D = N[u] is a wcd set. Therefore [[gamma].sub.wc](G) [less than or equal to] degu + 1 < n.

Case (iii): c(G) = 5.

G is a block with c(G) = 5 implies diam(G) [less than or equal to] 2. Then G has a proper wcd set as in the previous case. Therefore [[gamma].sub.wc](G) < n.

Case (iv): c(G) = 6.

G is a block with c( G) = 6 implies diam(G) [ess than or equal to] 3. If diam(G) [less than or equal to] 2, then G has a proper wcd set as in the previous cases. If diam(G) = 3, choose any x,y [member of] V(G) with xy [member of] E(G) and consider D = V(G) - {x,y}. Then (D) is connected and D is a dominating set (since G is a block). Therefore for any u,v G D there exists an u.. .v path in (D) Suppose there exists no u...v shortest path in (D). Then every u...v shortest path must pass through x,y.

[ILLUSTRATION OMITTED]

[ILLUSTRATION OMITTED]

Therefore [d.sub.<D>](u,v) > [d.sub.G](u,x) + [d.sub.G](x, y) + [d.sub.G](y,v) > 3. (i.e.) [d.sub.<D>](u/v) [greater than or equal to] 4. Hence there will exist a cycle of length at least 7...a contradiction (since c(G) = 6). Therefore there exists an u...v shortest path in D. D is a wcd set. Hence [[gamma].sub.wc](G) < n

Lemma. If G is a separable graph with ([delta](G) [greater than or equal to] 2 and 3 [less than or equal to] c(G) [less than or equal to] 6, then [[gamma].sub.wc](G) < n.

Proof. c(G) [less than or equal to] 6 implies c(B) [less than or equal to] 6 for any block B of G. Choose an end block B. Then B has at most one cut vertex.

Case (i): c(B) = 3.

In this case B' = {u} is a proper wcd set of B for any u [member of] V(B) (By the previous lemma). Choose u to be a cut vertex belonging to B. As B can contain at most one cut vertex, B' is a proper wcd set containing all cut vertices belonging to B. Therefore D = (V - B) [union] B' is a wcd set of G. (i.e.) [[gamma].sub.wc](G) [less than or equal to] n - [absolute value of B - B'] < n.

Case (ii): c(B) = 4.

Then diam(B) [less than or equal to] 2. If diam(B) = 1, then B' = {u} or B' = [N.sub.B] [u] is a wcd set for B for any cut vertex u [member of] B. (i.e) B' is a wcd set of B containing all cut vertices belonging to B. Therefore D = (V - B) [union] B' is a wcd set of G. Hence [[gamma].sub.wc](G) [less than or equal to] n - [absolute value of B - B'] < n.

Case (iii): c(B) = 5.

Then diam(B) [less than or equal to] 2. Then also B' = {u} or B' = [N.sub.B][u] is a proper wcd set for any cut vertex u belonging to B. Hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] [less than or equal to] n - [absolute value of B - B'] < n.

Case (iv): c(B) = 6.

Choose any two vertices x,y [member of] V(B) with xy [member of] E(B) and neither x nor y is a cut vertex. Such an edge exists since B is an end block with [deata](G) [greater than or equal to] 2. Let B' = V(B) - {x,y}. Then B' is a wcd set of B containing the cut vertex belonging to B. Therefore D = ( V - B) [union] B' is a wcd set of G. Therefore [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] [less than or equal to] n - [absolute valuen of B - B'] < n.

Observation. If G is a block with g(G) = 3 and c(G) [less than or equal to] 12 then [[gamma].sub.wc](G) < n.

Proof. Let C be a cycle of length 3 with V(C) = {[u.sub.i], [u.sub.2], [u.sub.3]}.

Case (i): N([u.sub.i]) [intersection] (V(G) - V(C)) = [PHI] for some [u.sub.i] [member of] V(C), i = 1, 2, 3, then D = V(G)-{[u.sub.i]} is a wcd set of G and hence [[gamma].sub.wc](G) < n.

Case (ii): N([u.sub.i])[intersection](V(G)-V(C)) [not equal to] [PHI] for each i [member of] {1, 2, 3}. Let [v.sub.1] [member of] N([u.sub.1])[intersection](V(G)-V(C)).

[ILLUSTRATION OMITTED]

G is a block implies there exists a cycle [C.sub.1] containing [u.sub.1][v.sub.1] (= e) and [u.sub.2]. Also N([u.sub.3]) [intersection] (V(G) - V(C)) [not equal to] [PHI]. Let [v.sub.2] [member of] N([u.sub.3]) [intersection] (V(G) - V(C)). Then there exists a cycle [C.sub.2] containing [u.sub.1] [v.sub.2] and [u.sub.3]. c(G) [less than or equal to] 12 implies l([C.sup.1]) (or) l([C.sup.2]) is less than or equal to 6. If l([C.sup.2]) [less than or equal to] 6 then choose x, y [member of] V([C.sub.2]) with xy [member of] E([C.sup.2] ) and x, y = {[u.sub.1], [u.sub.3]}. Then D = V(G) - {x, y} is a wcd set. Hence [[gamma].sub.wc](G) < n.

Observation. If G is a block with g(G) = 4 and c(G) [less than or equal to] 13 then [[gamma].sub.wc](G) < n.

Proof. Let C be a cycle of length 4 with V(C) = {[u.sub.1]: [u.sub.2], [u.sub.3], [u.sub.4]}.

Case (i): N([u.sub.i]) [intersection] (V(G) - V(C)) = [PHI] for some [u.sub.i], [member of] V(C).

Then D = V(G) - {[u.sub.4]} is a wcd set of G and hence [[gamma].sub.wc](G) < n.

Case (ii): N([u.sub.i]) [intersection] (V(G) - V(C)) [not equal to] [PHI] for each i [member of] {1, 2, 3, 4}. Let [v.sub.1] [member of] N([u.sub.1]) [intersection] (V(G) - V(C)). G is a block implies there exists a cycle [C.sup.1] containing e = [u.sub.1] [v.sub.1] and [u.sub.2].

[ILLUSTRATION OMITTED]

N([u.sub.4]) [intersection] (V(G) - V(C)) [not equal to] [PHI] implies there exists [v'.sub.1] [member of] N([u.sub.4]) [intersection] (V(G) - V(C)). Therefore there exists a cycle [C.sup.2] containing [u.sub.4][v'.sub.1] and [u.sub.3]. c(G) [less than or equal to] 13 implies l([C.sup.1]) or l([C.sup.2]) [less than or equal to] 6. Let l([C.sub.2]) [less than or equal to] 6. Then D = V(G) - {x,y} for any two x,y [member of] V([C.sup.2]) with xy [member of] x,y [not member of] {[u.sub.4], [u.sub.3]} is a wcd set. Therefore [[gamma].sub.wc](G) < n.

Observation. If G is block with g(G) = 5 and c(G) < 14, then [[gamma].sub.wc](G) < n.

Proof. Let C be a cycle of length 5 with V(C) = {[u.sub.1]: [u.sub.2], [u.sub.3], [u.sub.4], [u.sub.5]}.

Case (i): N (u) [intersection] (V(G) - V (C)) = [PHI] and N (v) [intersection] (V (G) - V (C)) = [PHI] for some u,v [member of] V (C) with uv [member of] E(C) then, D = V(G) - {u, v} is a wcd set. Therefore [[gamma].sub.wc](G) < n.

Case (ii): N(u) [intersection] (V(G) - V(C)) = [PHI] and N(v) [intersection] (V(G) - V(C)) = [PHI] for no two adjacent vertices u,v [member of] V(C). Let N([u.sub.5]) [intersection] (V(G) - V(C)) = [PHI]. Then N([u.sub.1]) [intersection] (V(G) - V(C)) = [PHI] and N([u.sub.4]) [intersection] (V(G) - V(C)) [not equal to] [PHI]. Let [v.sub.1] [member of] N([u.sub.1]) [intersection] (V(G) - V(C)). G is a block implies there exists a cycle [C.sup.1] containing e = [u.sub.1][v.sub.1] and [u.sub.2]. N([u.sub.4]) [intersection] (V(G) - V(C)) [not equal to] [PH] implies there exists [v.sub.1] [member of] N([u.sub.4]) [intersection] (V(G) - V(C)).

[ILLUSTRATION OMITTED]

Therefore there exists a cycle [C.sub.2] containing [u.sub.4][v'.sub.1] and [u.sub.3]. c(G) [less than or equal to] 14 implies l([C.sup.1]) or l([C.sup.2]) [less than or equal to] 6. Let l([C.sup.2]) [less than or equal to] 6. Then D = V(G) - {x, y} for any two x,y [member of] V(C2) with xy [member of] E([C.sup.2]) and x, y [member of] {[u.sub.4], [u.sub.3]} is a wcd set. Therefore [[gamma].sub.wc](G) < n.

Observation. If G is a block with g(G) = 6 and c(G) [less than or equal to] 15 then [[gamma].sub.wc](G) < n.

Proof. Let C be a cycle of length 6 with V(C) = {[u.sub.1]: [u.sub.2], [u.sub.3], [u.sub.4], [u.sub.5], [u.sub.6]}.

Case (i): N(u) [intersection] (V(G) - V(C)) = [PHI] and N(v) [intersection] (V(G) - V(C)) = [PHI] for some u, v [member of] V(C) with uv [member of] E(C), then, D = V( G) - {u, v} is a wcd set. Therefore [[gamma].sub.wc](G) < n.

Case (ii): N(u) n (V(G) - V(C)) = 4> and N(v) n (V(G) - V(C)) = 4> for no two adjacent vertices u,v e V(C). Let N(u6) n (V(G) - V(C)) = 4>. Then N([u.sub.1]) n (V(G) - V(C)) = [PHI] and N([u.sub.5]) [intersection] (V(G) - V(C)) [not equal to] [PHI].

Let [v.sub.1] [member of] N([u.sub.1] ) [intersection] (V(G) - V(C)). G is a block implies there exists a cycle [C.sup.1] containing e = [u.sub.1][v.sub.1] and [u.sub.2].

[ILLUSTRATION OMITTED]

N([u.sub.5]) [intersection] (V(G) - V(C)) [not equal to] [PHI] implies there exists [v'.sub.1] [member of] N([u.sub.5]) [intersection] (V(G) - V(C)). Therefore there exists a cycle [C.sup.2] containing [u.sub.5][v'.sub.1] and [u.sub.4]. c(G) [less than or equal to] 14 implies l([C.sup.1]) or l([C.sup.2]) [less than or equal to] 6. Let l([C.sup.2]) [less than or equal to] 6. Then D = V(G) - {x,y} for any two x,y [member of] V([C.sup.2]) with xy [member of] E([C.sup.2]) and x,y [member of] {[u.sub.4], [u.sub.5]} is a wcd set. Therefore [[gamma].sub.wc](G) < n.

Definition. [7] A graph G is distance-hereditary if for all connected induced subgraphs F of G, [d.sub.F](u, v) = [d.sub.G](u, v) for all u,v [member of] V(F).

Observation. For every distance hereditary graph G, [[gamma].sub.wc](G) < n.

Proof. Consider any spanning tree [T.sub.G] of [T.sub.G]. Then <V([T.sub.G]) - A> where A is the set of all pendant vertices of [T.sub.G] is distance preserving. (i.e.) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all x, y [member of] V([T.sub.G]) - A. Therefore for every x, y [member of] V([T.sub.G]) - A there exists an x ... y shortest path in <V([T.sub.G]) - A). Also V([T.sub.G]) - A is a dominating set. Hence [[gamma].sub.wc](G) < n

CHARACTERIZATIONS

We use the following notations throught the remaining discussion.

Notation. Ta denote any spanning tree of G.

A - denote the set of all pendant vertices in [T.sub.G].

[T'.sub.G] denote the subtree obtained by deleting all pendant vertices from [T.sub.G]. (i.e.) [T'.sub.G] = [T.sub.G] - A.

[T".sub.G] denote the subtree obtained by deleting a proper subset A' [subset] A from [T.sub.G]. (i.e.) [T".sub.G] = [T.sub.G] - A'.

<V([T'.sub.G])> denote the subgraph of G induced by V([T".sub.G]).

<V([T".sub.G])> denote the subgraph induced by V([Ta".sub.G]).

Definition. A subset V(H) of V(G) is said to be distance preserving if [d.sub.<V(H)>] (x,y) = [d.sub.G](x,y) for all x,y [member of] V(H).

Remark. If G has a wcd set D, then for every x, y [member of] D there exists an x ... y shortest path in <D>. [d.sub.<D>](x,y) = da(x,y) for all x,y [member of] D and hence D is distance preserving.

Example.

[ILLUSTRATION OMITTED]

Here [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example.

[ILLUSTRATION OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[ILLUSTRATION OMITTED]

Example.

Here A = {3, 8, 9,10,11, 6}. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all x,y [member of] V([T'.sub.G]) (since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [d.sub.G] (4, 7) = 2). A' = {3, 9, 11, 6} then A' [subset] A. [T".sub.G] is not distance preserving. But <V([T".sub.G])> is distance preserving.

Observation. If [delta](G) = 1 then [[gamma].sub.wc](G) < n as D = V(G) - {u [member of] V(G)/degu = 1} is a wcd set.

Observation. If G is a graph with [delta](G) [greater than or equal to] 2, then [[gamma].sub.wc](G) < n if and only if G is a tree or G has a spanning tree [T.sub.G] satisfying one of the following three conditions:

(i) [T.sub.G] has a subtree [T'.sub.G] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all x,y [member of] V([T'.sub.G]).

(ii) [T.sub.G] has a subtree [T'.sub.G] such that <V([T'.sub.G])> is distance preserving.

(iii) [T.sub.G] has a subtree T '' such that <V([T".sub.G])> is distance preserving.

Proof. [[gamma].sub.wc](G) < n implies that there exists a proper wcd set D. Then D is a dominating set with (D) is connected and distance preserving. (D) is connected implies <D> has a spanning tree T<D>. Hence D = V([T.sub.<D>]) and each vertex in V - D is adjacent to some vertex in V([T.sub.<D>]). Deleting the edges in <V - D> we get a spanning tree [T.sub.G] of G. (i.e.) there exists a spanning tree [T.sub.G] of G such that D = V([T.sub.G]) - A' where A' [subset of equal to] A and <D> = <V(Ta) - A'> is distance preserving.

Case (I): <D> = <V(T - A')> = [T'.sub.G] with [T'.sub.G] is distance preserving and A = A'.

I - (i): <A> is independent.

If u [member of] A then there exists [u.sub.1] [member of] D = V( [T'.sub.G]) such that u[u.sub.1] [member of] E(G). [delta](G) [greater than or equal to] 2 implies there exists [u.sub.2]([not equal to] [u.sub.1]) [member of] V(G) such that [u.sub.2] [member of] N(u). A is independent implies [u.sub.1], [u.sub.2] [member of] D = V([T'.sub.G]). Therefore there exists an [u.sub.1]...[u.sub.2] shortest path in <D> = [T'.sub.G]. (i.e.) there exists an [u.sub.1]...[u.sub.2] shortest path in the subtree [T'.sub.G].

Therefore if u,v [member of] A then [absolute value of N (u) [intersection] V ([T'.sub.G])] > 1 and [absolute value of N (v) [intersection] V ([T'.sub.G])] > 1. Hence if [u.sub.1] [member of] [absolute value of N (u) [intersection] V ([T'.sub.G])] > 1 and [v.sub.1] [member of] [absolute value of N (v) [intersection] V ([T'.sub.G])] > 1 then there exists an [u.sub.1] ... [v.sub.1] shortest path in [T'.sub.G]. (i.e) every shortest path connecting u snd v should pass through the points of [T'.sub.G] and [T'.sub.G] is a distance preserving subtree. Therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [T'.sub.G] is a distance preserving subtree implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (i.e.) [T.sub.G] is a distance preserving spanning tree of G. Hence no two pendant vertices of TG are adjacent in G (since if u, v are pendant vertices in TG with uv e E( G) then 1 = dG(u, v) < dT (u, v)). TG' is distance preserving implies no two pendant vertices of TG' are adjacent in G. Similarly no two pendant vertices in the tree obtained by removing the pendant vertices of TG' are adjacent. Proceeding like this we get G as an acyclic connected graph. Hence G is a tree.

I - (ii): <A> is not independent.

<A> is not independent implies there exist at least two adjacent vertices u, v in <A>. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (i.e.) [T.sub.G] is not distance preserving. But [T'.sub.G] is distance preserving. Hence G has a spanning tree [T.sub.G] with distance preserving subtree [T'.sub.G]. Hence condition (ii) is satisfied.

Case (II): D = V([T'.sub.G]) and [T'.sub.G] is not distance preserving. A' may or may not be independent and A = A'.

<D> = <V(TG) - A> = <V([T.sub.G'])> is distance preserving. (i.e.) G has a spanning tree TG with a subtree [T.sub.G'] such that the subgraph induced by V([T'.sub.G]) is distance preserving. Hence condition (iii) is satisfied.

Case (III): [T'.sub.G] is not distance preserving and A' [subset] A and A' may or may not be independent.

Then <D> = <V(TG) - A'> is distance preserving. (i.e) <V([T".sub.G])> is distance preserving. (i.e.) G has a spanning tree [T.sub.G] with subtree [T".sub.G] such that <V([T".sub.G])> is distance preserving. Hence condition (iv) is satisfied.

Conversely, suppose G is a tree or G has a spanning tree [T.sub.G] satisfying one of the conditions (i) to (iii).

If G is a tree then D = V(G) - A where A is the set of all pendant vertices of G is a wcd set of G.

If G has a spanning tree [T.sub.G] satisfying condition (i) or (ii) then D = V([T.sub.G]) - A is a wcd set of G.

If G has a spanning tree TG satisfying condition (iii) then D = V( TG ) - A' is a wcd set of G.

Hence [[gamma].sub.wc](G) < n in all cases.

CONSTRUCTION OF A GRAPH G WITH [[gamma].sub.wc](G) < n.

Observation. [[gamma].sub.wc](G) < n if and only if G can be constructed as follows:

Take any connected graph H.

(i) Attach one or more pendant vertices at each (or at some) vertices of H.

(ii) Identify an edge of a cycle at each (or some) edges of H.

(iii) Identify two consecutive edges of a 4 cycle at each (or some) paths of length 2 in H.

(iv) Do any one or both of the two operations (i) and (ii) at each (or some) vertices of H and do operation.

(iii) At each (or at some) paths of length 2 in H.

(v) Attach one or more triangles at each (or at some) vertices of V(H).

(vi) Identify an edge of a 4 cycle at each (or some) edge of H.

(vii) Identify two consecutive edges of a 5 cycle at each (or some) paths of length 2 in H.

(viii) Identify three consecutive edges of a 6 cycle at each (or some) paths of length 3 in H.

(ix) Do any one of the operations (v) to (viii) at each (or some) vertex, edge, paths of length 2 or 3.

(x) Do all (or some) of the operations (i) to (ix) at each (or some) vertex, edge, paths of length 2, paths of length 3.

(xi) Take any two connected graphs H and H' with V(H) = {[u.sub.1], [u.sub.2], ..., [u.sub.r]} and V(H') = {[v.sub.1],[v.sub.2],...,[v.sub.s]}. First join [v.sub.1] to [u.sub.1]. Join each [v.sub.i] [member of] [N.sub.H'] ([v.sub.1]) to [u.sub.1] or to all or some vertices which are at distance atmost 3 from [u.sub.1] in H. (i.e.) each [v.sub.1] [N.sub.H'] ([v.sub.1]) can be joined to [u.sub.1] or to all or some u with [d.sub.H]([u.sub.1],[u.sub.i]) [less than or equal to] 3. Do the same operation for each [v.sub.j] [member of] [N.sub.H']([v.sub.i]) and repeat this process until each [v.sub.i] is joined to some [u.sub.i].

(xii) Take any connected graph H and any number of connected graphs {[H'.sub.i]} and perform the operation (xi) to each [H'.sub.i].

Proof. Let [[gamma].sub.wc](G) < n and let D be a [[gamma].sub.wc] set of G. Then <D> is connected and distance preserving.

Case (i): [delta](G) = 1 and <V - D> is independent.

Hence in this case G can be obtained by taking H = <D> and attaching one or more pendant vertices at each or some vertices of H.

Case (ii): [delta](G) [greater than or equal to] 2 and <V - D> is independent.

[delta](G) [less than or equal to] 2 and <V - D> is independent implies for every u [member of] V - D, [absolute value of N (u) [intersection] D] [greater than or equal to] 2. Let [u.sub.1],[u.sub.2] [member of] N (u) [intersection] D. Then d([u.sub.1],[u.sub.2]) [less than or equal to] 2. <D> is a wcd set implies there exists an [u.sub.1]...[u.sub.2] shortest path of length [less than or equal to] 2 in (D).

[ILLUSTRATION OMITTED]

Therefore, G can be obtained by taking a connected graph <D> and performing one of the operations (ii) to (iv).

Case (ii): The components of <V - D> are [K.sub.2] alone.

For any two u, v [member of] V - D with uv [member of] E(G) both of them may be adjacent to a same vertex or adjacent to two different vertices in D. If each pair of adjacent vertices in V - D are adjacent to the same vertex in D then in this case G can be obtained by taking H = <D> and performing the operation (v). If there exists u,v [member of] V - D with uv [member of] E(G) and adjacent to two different vertices [u.sub.1] and [v.sub.1] respectively in D, then d([u.sub.1], [v.sub.1]) [less than or equal to] 3. D is a wcd set implies there exists an [u.sub.1] ... [v.sub.1] shortest path of length [less than or equal to] 3 in (D).

[ILLUSTRATION OMITTED]

Therefore, G can be obtained by taking a connected graph H = <D> and performing one of the operations (v) to (ix).

Case (iii): The components of <V - D> are isolates and [K.sub.2]s.

In this case G can be obtained by taking H = <D> and performing the operation (ix).

Case (iv): <V - D> is connected.

In this case, G can be obtained by taking H = (D) and performing one of the operations (x).

Case (v): <V - D> is disconnected and has more than one connected components.

In this case, G can be obtained by taking H = <D> and performing operation (xi) to each connected graph [H'.sub.i].

Lemma. If G is any simple graph with n [greater than or equal to] 3 and [delta](G) [greater than or equal to] n/2 then [[gamma].sub.wc](G) < n.

Proof. For any vertex u of degree [delta] consider D = N[u]. Then any v [member of] V - D must be adjacent to some [u.sub.i] [member of] N(u), since v is not adjacent to u. Otherwise [delta](G) [less than or equal to] deg v [less than or equal to] n - 1 - [absolute value of N(u)] = n - 1 - [delta] [less than or equal to] n - 1 - n/2 < n/2 ... a contradiction to the fact that [delta] [greater than or equal to] n/2. Therefore, each v g V - D is adjacent to some [u.sub.i] [member of] N(u) and hence D is a dominating set. And D = N[u] implies [d.sub.<D>](x,y) = [d.sub.<G>](x,y) for all x,y [member of] D. (i.e.) D is a wcd set and hence [[gamma].sub.wc](G) < n.

Corollary. If [[gamma].sub.wc](G) = n then [delta](G) < n/2.

Proof. For if [delta](G) [greater than or equal to] n/2 then by the previous lemma [[gamma].sub.wc](G) < n... a contradiction (since [[gamma].sub.wc](G) = n).

Lemma. If [delta](G) [greater than or equal to] n/2, then [[gamma].sub.wc](G) [less than or equal to] [delta] + 1 or [[gamma].sub.wc](G) = 2.

Proof. [delta](G) [greater than or equal to] n/2 implies G is Hamiltonian [6]. And m = 1/2[summation]deg u = [n.sup.2]/4. Therefore, G is pancyclic (or) G is [K.sub.n/2n/2] [6]. If G is pancyclic, then D = N[u] is a wcd set with deg u = [delta]. Therefore, [[gamma].sub.wc](G) [less than or equal to] [delta] + 1. If G is [K.sub.n/2n/2] then [[gamma].sub.wc](G) = 2.

Observation. [[gamma].sub.wc](G) = n if and only if G is not a tree and for every spanning tree [T.sub.G] and for every subset A' [subset or equal to] A there exists at least one pair of points x,y [member of] V([T.sub.G]) - A' such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Let [[gamma].sub.wc](G) = n. Then G cannot be a tree. If there exists a spanning tree [T.sub.G] and a set of pendant vertices A' [subset or equal to] A such that for every x,y [member of] V([T.sub.G]) - A', [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then D = V([T.sub.G]) - A' is a proper wcd set of G... a contradiction.

Conversely, suppose G is not a tree and for every spanning tree [T.sub.G] and for every subset A' [subset of equal to] A there exists at least one pair of points x,y [member of] V([T.sub.G]) - A' such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let if possible [[gamma].sub.wc](G) < n. Then G is a tree (or) has a spanning tree [T.sub.G] with a set of pendant vertices A' [subset or equal to] A such that for every pair of points x,y [member of] V([T.sub.G]) - A', [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (by observation (12)... a contradiction).

Observation. [gamma](G) = [[gamma].sub.wc](G) if and only if G is a caterpillar (or) G has a spanning tree [T.sub.G] with maximum number of pendant edges [[epsilon].sub.T](G) satisfying one of the two conditions (a) or (b) and both the coditions (c) and (d).

(a) [T.sub.G] has a distance preserving subtree [T'.sub.G].

(b) [T.sub.G] has a subtree [T'.sub.G] with <V([T'.sub.G])> is distance preserving.

(c) Each u [member of] V(G) is either a support or a pendant vertex in [T.sub.G].

(d) The domination number of G is the number of supports in [T.sub.G].

Proof. Let [gamma](G) = [[gamma].sub.wc](G) and let D be a [[gamma].sub.wc] set. Then D is a connected dominating set. Therefore, [gamma]c(G) [less than or equal to] [[gamma].sub.wc](G) = [gamma](G). But [gamma](G) [less than or equal to] [[gamma].sub.c](G) [less than or equal to] [[gamma].sub.wc](G). Therefore, [[gamma].sub.c](G) = [[gamma].sub.wc](G) = [gamma](G). [[gamma].sub.c](G) = n - [[epsilon].sub.T](G) where [[epsilon].sub.T](G) is the number of pendant vertices in a spanning tree of G with maximum number of pendant edges. Therefore, n - [[epsilon].sub.T](G) = [[gamma].sub.c](G) = [[gamma].sub.wc](G) = [gamma](G)....

(i) G has a proper wcd set. Therefore, G is a tree or has a spanning tree [T.sub.G] satisfying one of the three conditions of observation 12. (i.e.) G is a tree or there exists a spanning tree [T.sub.G] such that D = V([T.sub.G]) - A' for some A' [subset or equal to] A with <V(TG> - A'> is distance preserving.

(ii) [absolute value of D] = [[gamma].sub.wc](G) = [gamma](G) implies N(u) [intersecton] (V - D) [not equal to] [PHI] for each u [member of] D (since D is a minimum dominating set and G is connected).

(iii) By (i) and (ii) n - [[epsilon].sub.T](G) = [absolute value of D] = [absolute value of V([T.sub.G]) - A']. Therefore [absolute value A'] = [[epsilon].sub.T](G). (i.e) [[epsilon].sub.T](G) = [absolute value of A'] [less than or equal to] [absolute value of A] [less than or equal to] [[epsilon].sub.T]. Hence [[epsilon].sub.T](G) = [absolute value A'] = [absolute value A]. (i.e.) G is a tree or has a spanning tree [T.sub.G] with maximum number of pendant edges equal to [absolute value of A'] and <D> = <V([T.sub.G]) - A'> = <V(TG) - A> is distance preserving. Hence by (iii) each u [member of] D = V([T.sub.G]) - A is a support and each u [member of] V - D = A is a pendant vertex in [T.sub.G]. (i.e.) G is a tree or G has a spanning tree [T.sub.G] with distance preserving subtree [T'.sub.G] (or) has a subtree [T'.sub.G] with <V([T'.sub.G])> is distance preserving. (ie) G is a tree (or) satisfies one of the two conditions (a) and (b).

If u [member of] V(G) then either u [member of] D (or) u [member of] V - D. (i.e.) either u is a support (or) a pendant vertex in G (or) [T.sub.G]. Hence, if G is a tree then G is a caterplillar. If G is not a tree then [T.sub.G] satisfy condition (c). [GAMMA](G) = [[gamma].sub.wc](G) = [absolute value of D] = number of supports in [T.sub.G]. Hence condition (d) is satisfied.

Conversely, suppose G is a tree or has a spanning tree satisfying one of the two conditions (a) or (b) and both the coditions (c) and (d).

If G is a tree and satisfying conditions (c) and (d), then D = V(G) - A where A is the set of all pendant vertices is a wcd set and hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D]. G satisfies conditions (c) and (d) implies each u [member of] D = V(G) - A is a support and [gamma](G) = [absolute value of D]. Hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = [gamma](G).

(i.e.) [GAMMA](G) = [[gamma].sub.wc](G).

If G satisfies conditions (a), (c) and (d), then <D> = <V([T.sub.G]> - A> = [T.sub.G] is a distance preserving subtree of [T.sub.G] with A as the set of all pendant vertices of [T.sub.G]. (i.e) D is a wcd set and hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D]. That [T.sub.G] satisfies condition (c) and (d) implies each u [member of] [absolute value of D] = V([T.sub.G]) - A is a support and [gamma](G) = [absolute value of D]. Hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = [gamma](G). (i.e.) [gamma](G) = [[gamma].sub.wc](G).

If G satisfy conditions (b), (c) and (d), then <D> = <V([T.sub.G]> - A) = <V([T.sub.G])> is distance preserving. (i.e) D is a wcd set and hence [[gamma].sub.wc](G) [less than or equal to] [absolute vlaue of D]. [T.sub.G] satisfy conditions (c) and (d) implies each u [member of] D = V([T.sub.G]) - A is a support and [gamma](G) = [absolute value of D]. Hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = [gamma](G). (i.e.) [gamma](G) = [[gamma].sub.wc](G).

CONSTRUCTION OF GRAPHS WITH [gamma](G) = [[gamma].sub.wc](G).

Observation. [gamma](G) = [[gamma].sub.wc](G) if and only if G is a caterpillar (or) G can be obtained as follows:

Take any connected graph which is not a path H and consider a spanning tree [T.sub.H] of H with maximum number of pendant edges. Let {[u.sub.1],[u.sub.2],..., [u.sub.r]} be the set of pendant vertices of [T.sub.H]. Attach one or more pendant vertices at each u [member of] V (G) - {[u.sub.1], [u.sub.2],..., [u.sub.r]} and let {[v.sub.1], [v.sub.2],...,[v.sub.s]} be the set of pendant vertices thus attached and [T.sub.G] be the resulting tree.

If u [member of] N([v.sub.i]) [intersection] V(H) then [v.sub.i] can be joined to each or some v [member of] V(H) with [d.sub.H](u,v) [less than or equal to] 2. Any two vis can be joined if both of them are adjacent to a same vertex in H. Join [v.sub.i] and [v.sub.j] if [d.sub.H](u, v) [less than or equal to] 3 where u [member of] N([v.sub.i]) [intersection] V(H) and v [member of] N([v.sub.j]) [intersection] V(H).

Proof. Let [gamma](G) = [[gamma].sub.wc](G). Then, by the previous observation, G is a caterpillar (or) G has a spanning tree [T.sub.G] satisfying conditions (a) (or) (b) and both the conditions (c) and (d). Let H = <V([T'.sub.G])> - the set of pendant vertices of [T'.sub.G]. Then H satisfy the required conditions.

Conversely, if G is constructed by the above method then let D = V(H) - {[u.sub.1]: [u.sub.2],..., [u.sub.r]}. Then [T.sub.G] is a spanning tree of G with maximum number of pendant edges and D is a wcd set. Hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = n - [[epsilon].sub.T]. Therefore [[gamma].sub.wc](G) = n - [[epsilon].sub.T] [less than or equal to] [gamma](G). (i.e.) [gamma](G) = [[gamma].sub.wc](G).

Observation. [[gamma].sub.c](G) = [[gamma].sub.wc](G) if and only if G is a tree or has a spanning tree [T.sub.G] with maximum number ct of pendant edges satisfying one of the following two conditions:

(i) [T.sub.G] has a distance preserving subtree [T'.sub.G].

(ii) [T.sub.G] has a subtree [T'.sub.G] such that <V([T'.sub.G])> is distance preserving.

Proof. Let [[gamma].sub.c](G) = [[gamma].sub.wc](G). If D is a [[gamma].sub.wc] set then G satisfy one of the four conditions of observation 12. (i.e.) G is a tree (or) <D> = <V([T.sub.G]) - A'> where A' [subset or equal to] A and <D> is distance preserving. n - [[epsilon].sub.T] = [[gamma].sub.c](G) = [[gamma].sub.wc](G) = [absolute value of D] = [absolute value of V([T.sub.G]) - A'] = n - [absolute value of A'] which implies [[epsilon].sub.T] = [absolute value of A'] [less than or equal to] [absolute value of A] [less than or equal to] [[epsilon].sub.T]. Therefore [[epsilon].sub.T] = [absolute vlaue of A'] = [absolute vlaue of A]. (i.e.) [T.sub.G] is a spanning tree of G with maximum number of pendant edges. Hence G has a spanning tree [T.sub.G] with maximum number of pendant vertices satisfying one of the two conditions.

Conversely, if G is a tree then [[gamma].sub.c](G) = [[gamma].sub.wc](G).

If G has a spanning tree with maximum number of pendant edges satisfying one of the two conditions then D = V([T.sub.G]) - A is a wcd set with [absolute value of A] = [[epsilon].sub.T] and hence [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = [absolute value of V([T.sub.G]) - A] = n - [absolute value of A] = n - [[epsilon].sub.T] = [[gamma].sub.c](G). Hence [[gamma].sub.c](G) = [[gamma].sub.wc](G).

CONSTRUCTION OF A GRAPH WITH [[gamma].sub.c] (G) = [[gamma].sub.wc](G).

[[gamma].sub.c](G) = [[gamma].sub.wc](G) if and only if G is either [G.sub.1] (or) [G.sub.2] which are obtained as follows:

Take any connected graph H and consider a spanning tree [T.sub.H] with maximum number of pendant edges and let B = {[u.sub.1],[u.sub.2],..., [u.sub.r]} be the set of pendant vertices of [T.sub.H]. Attach one or more pendant vertices at each [u.sub.i], 1 [less than or equal to] i [less than or equal to] r. Let A = {[v.sub.1], [v.sub.2],..., [v.sub.s]} with s [greater than or equal to] r be that set of pendant vertices thus attached. Let [G.sub.1] be the resulting graph.

In [G.sub.1] connect [v.sub.i] [member of] N([u.sub.i]) and [v.sub.j] [member of] N([u.sub.j]) by a path such that d([u.sub.i], [u.sub.j]) [less than or equal to] d([v.sub.i], [v.sub.j]) and let [G.sub.2] be the resulting graph.

Proof. Let [[gamma].sub.c](G) = [[gamma].sub.wc](G). Then by the previous observation G is a tree or G has a spanning tree satisfying the two conditions.

If G is a tree then G is of the form [G.sub.1].

If G has a spanning tree [T.sub.G] with maximum number of pendant edges and a distance preserving subtree [T.sub.G], then <D> = <V([T.sub.G]) - A> = [T.sub.G]. Let A = {[v.sub.1], [v.sub.2],..., [v.sub.s]}. Now let B = {[u.sub.1], [u.sub.2],..., [u.sub.r]} be the set of pendant vertices of [T.sub.G]. In this case (A) is not independent. Therefore G can be obtained by taking a tree and attaching one or more triangles at each [u.sub.i], 1 [less than or equal to] i [less than or equal to] r. (i.e.) G is of the form [G.sub.2].

If G has a spanning tree [T.sub.G] with maximum number of pendant edges and a subtree [T'.sub.G], with <V([T.sub.G])> is distance preserving. Then <D> = <V([T.sub.G]) - A> = [T.sub.G]. Let A = {[v.sub.1], [v.sub.2], ..., [v.sub.s]} and let B = {[u.sub.1],[u.sub.2],..., [u.sub.r]} be the set of pendant vertices of [T.sub.G]. Then [T.sub.G] is a spanning tree of <D> with maximum number of pendant edges. For if there exists any other spanning tree [T'.sub.<D>] of <D> with t number of pendant vertices and t > r. Each [v.sub.i] is adjacent to some vertex in [T'.sub.<D>]. t > r implies there exists a spanning tree [T.sub.1G] of G with more number of pendant vertices than the number of pendant vertices in [T.sub.G] which is a contradiction to the fact that [T.sub.G] is a spanning tree with maximum number of pendant vertices.

Now let <D> = H. If [v.sub.i] [member of] N([u.sub.i]) then d([u.sub.i], [u.sub.j]) [less than or equal to] d([v.sub.i]; [v.sub.j]) (since D is a wcd set).

If <V - D> is independent then G is of the form [G.sub.1].

If <V - D> is not independent then G is of the form [G.sub.2].

Conversely, suppose G is of the form [G.sub.1] or [G.sub.2].

Then let D = V(H). By construction [[gamma].sub.c](G) = n - [[epsilon].sub.T](G) = [absolute value of V(H)] = [absolute value of D] and D is a wcd set. Therefore [[gamma].sub.wc](G) [less than or equal to] [absolute value of D] = [[gamma].sub.c](G). Hence [[gamma].sub.c](G) = [[gamma].sub.wc](G).

Definition. For any connected graph G we define,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where A is the set of all pendant vertices in a spanning tree [T.sub.G] of G.

Observation. [[gamma].sub.wc](G) [less than or equal to] n - [[epsilon].sub.max].

Observation. If G is a block with proper wcd set then [[gamma].sub.wc](G) = n - [[epsilon].sub.max].

Proof. If D is a [[gamma].sub.wc] set of G, then D = V([T.sub.G]) - A' with A' [subset or equal to] A. Therefore [[gamma].sub.wc](G) = [absolute value of D] = [absolute value of V([T.sub.G]) - A'] [greater than or equal to] n - [[epsilon].sub.max] (since [absolute value of A'] [less than or equal to] [[epsilon].sub.max]). Therefore by the previous observation [[gamma].sub.wc](G) = n - [[epsilon].sub.max].

References

[1] Acharya. B. D., Purnima Gupta, On Point - set domination in graphs, Proc. Nat. Seminar on Recent Development in Mathematics, N. M. Bujurke (Ed.), Karnataka University Press, Dharwad, 1996, 106-108.

[2] Acharya. B. D., Purnima Gupta, On Point - set dominiation in graphs: II minimum psd - sets, J. Combin. Theory Ser. B, 1996.

[3] Acharya. B. D., Purnima Gupta, On Point set domination in graphs: III Further details submitted.

[4] Acharya. B. D., Purnima Gupta, On Point set domination in graphs: IV Seperable graphs with unique minimum psd-sets, Discrete Mathematics, 195(1999), 1-13.

[5] S. Arumugam and R. Kala, Domination Parameters of a star Graph, ARS Combinatoria, 44(1996), 93-96.

[6] Balakrishnan. R., Ranganathan. K., A text book of Graph Theory, Springer Verlag, New York, 2000.

[7] Fred Buckley, Fred Harary, Distance in Graphs, Addission - Wesley Publishing Company, 1990.

[8] Gary Chartrand, Curtiss E. Wall and Ping Zhamg, The convexity Number of a Graph, Graphs and Combinatorics, 18(2002), 209-217.

[9] Gary Chartrand, Frank Harary, Henda C. Swart, Geodomination in Graphs, Bulletin of the ICA, 31(2001), 51-59.

[10] F. Harary, Graph Theory, Addison - Wesley, 1969.

[11] T. Haynes, S. T. Hedetniemi and P. J. Slater, Advances in the Theory of Domination in Graphs, Marcel Dekker Incl, New York, 1997.

[12] S. M. Hedetniemi, S. T Hedetniem, D. F. Rall, Acyclic domination, Discrete Mathematics, 222(2000), 151-165.

[13] V. R Kulli and B. Janakiram, The Non Split domination number of a graph, Indian J. Pure appl. Math, 2000, 441-447.

[14] Parthasarathy. K. R., Basic Graph Theory, Tat McGraw-Hill Publishing Company Limited, 1994.

[15] Sampathkumar. E., Point set domination Number of a graph, Indian J. Pure Appl. Math., 4(1993), 225-229.

[16] E. Sampathkumar (Ed.), Graph Theory Research Report, Karnatak University, Dhar wad, No. 3, 1972.

[17] H. B. Walikar, B. D. Acharya and E. Sampathkumar, Recent Advances in the theory of domination in graphs and its applications, MRI Lecture Notes in Mathematics, Mehta Research Institute of Mathematics and Mathematical Physics, Allahabad, No. 1, 1979.

[18] Wayne Goddard and Michael A. Henning, Domination in planar Graphs with small Diameter, Journal of Graph Theory, 2002, 1-25.

R. Poovazhakit ([dagger]) and V. Swaminathan ([double dagger])

([dagger]) Department of Mathematics, EMG Yadava Women's College, Madurai

625014, India

([double dagger]) Department of Mathematics, Saraswathi Narayan College, Ma durai

625022, India

E-mail: rpoovazhaki@yahoo.co.in sulanesri@yahoo.com
COPYRIGHT 2011 American Research Press
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Poovazhaki, R.; Swaminathan, V.
Publication:Scientia Magna
Article Type:Report
Geographic Code:9INDI
Date:Jan 1, 2011
Words:11512
Previous Article:Generalized Weyl's theorem for Class A operators.
Next Article:New hybrid filtering techniques for removal of speckle noise from ultrasound medical images.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |