PDF《Pure Mathematical Sciences, Vol. 1》

2 for every v ∈ N(u) then u is in every equitable dominating set such vertices are called an equitable isolated. Ie denotes the set of all equitable isolated. Let G = (V, E) be a graph and let u ∈ V the equitable neighborhood of u denoted by Ne(u) is de?ned as Ne(u) = {v ∈ V : |v ∈ N(u), |deg(u)?deg(v)| ≤ 1}. The maximum and minimum equitable degree of a vertex in G are denoted by Δe(G) and δe(G) that is Δe(G) = maxu∈V |Ne(u)| and δe(G) = minu∈V |Ne(u)|. The open equitable neighbourhood and closed equitable neighbourhood of v are denoted by Ne(v) and Ne[v] = Ne(v) ∪ {v} respectively. If S ? V then Ne(S) = ∪v∈SNe(v) and N[S] = Ne(S) ∪ S. If S ? V and u ∈ S then the private equitable neighbor set of u with respect to S is de?ned by pne[u, S] = Ne[u] ? Ne[S ? {u}]. If G is connected graph, then a vertex cut of G is a subset R of V with the Connected equitable domination

125 property that the subgraph of G induced by V ?R is disconnected. If G is not a complete Graph, then the vertex connectivity number k(G) is the minimum cardinality of a vertex cut. It is a convention that if G is complete graph Kp it is known that k(G) = p ? 1.

2 Connected Equitable Domination In Graphs De?nition. Let G = (V, E) be a connected graph. An equitable dominating set S of a graph G is called the connected equitable dominating set (ced-set) if the induced subgraph S is connected the minimum cardinality of a ced-set of G is called the connected equitable domination number of G and is denoted by γce(G). We supposed that G is connected because if the graph has more than one component the equitable dominating set has at least one vertex from every component of G and then D is not connected, and conversely if G has a minimum connected equitable dominating set D and hence connected equitable number then then D is connected that means G is connected according to that we state the following observation. Theorem 2.1 A connected equitable dominating set exist for a graph G if and only if G is connected. Example. Let G be a graph as in the Figure 1, we can ?nd the domina- tion number, connected domination number, equitable domination number and connected equitable domination number as the following: γ(G) = 1, γe(G) = 4, γce(G) =

5 and γc(G) = γ(G) =

2 t t u v v v Figure

1 In the following Theorem the proof is straightforward from the de?nition of the connected equitable domination number of a graph. Theorem 2.2 The connected equitable domination number of some stan- dard graphs are

126 S. Sivakumar, N. D. Soner, Anwar Alwardi and G. Deepak 1. γce(Kp) =

1 2. γce(Pp) = p ?

2 3. γce(Cp) = p ?

2 4. γce(Wp)= p+3

3 , if p ≥ 6;

1, otherwise. 5. γce(Kr,t)= ? ? ? ? ? 1, if either r or t=1 ;

2, if |r ? t| ≤

1 and r,t ≥ 2;

r + t, if |r ? t| ≥

2 and r,t ≥ 2. The join G = G1 + G2 of graphs G1 and G2 and with disjoint vertex sets V1 and V2 and edge sets E1 and E2 is the graph union G1 ∪ G2 together with all the edges joining V1 and V2. For example Wp = Cp?1 + K1. Theorem 2.3 For any graph G, γce(Kp +H) =

1 if and only if H is regular or (k, k +1) bi-regular graph( a graph which all of its vertices has either degree k or k + 1). Proof. Let the number of vertices in H is p and let G = Kp + H. we can labeling the vertices of G as v1, v2, ..., vp, v1, v2, ..., vp which v1, v2, ..., vp the vertices of Kp and v1, v2, ..., vp the vertices of H. Now if H is complete then clearly any vertex in G is equitable adjacent to all the vertices of G. Similarly if H regular or (k, k + 1) bi-regular graph any vertex in vi where i = 1, 2, ..., p is equitable adjacent to all the other vertices in G. Hence γce(Kp + H) = 1. Conversely, if γce(Kp + H) = 1, then there is a vertex u in G which equitable adjacent all the other vertices in G we have two cases: Case 1: u ∈ {v1, v2, ..., vp}, then |deg(u) ? deg(vi)| ≤