PDF《Pure Mathematical Sciences, Vol. 1》

1 for all i = 1, 2, ..., p , that means |p ?

1 + p ? degH(vi) ? p| ≤

1 where degH(vi) is the degree of the vertex vi in the graph H and i = 1, 2, ..., p . Hence |p ? degH(vi)| ≤

2 that means p ? degH(vi) ≤ 2. Therefore degH(vi) ≥ p ? 2. Hence H is either regular or bi-regular graph. Case 2: similarly as in Case

1 if u ∈ v1, v2, ..., vp , we get that H is regular or bi-regular. Theorem 2.4 For any connected graph G, γ(G) ≤ γe(G) ≤ γce(G) Proof. From the de?nition of the connected equitable dominating set of a graph G, it is clearly that for any graph G any connected equitable dominating set D is also an equitable dominating set and every equitable dominating set is also dominating set. Hence γ(G) ≤ γe(G) ≤ γce(G). Similarly since every connected equitable dominating set for any connected graph G is connected dominating set we have the following Theorem. Connected equitable domination

127 Theorem 2.5 For any connected graph G, γc(G) ≤ γce(G). . Theorem 2.A.[2] For any graph G with p vertices, p

1 + Δe(G) ≤ γe(G) ≤ p ? Δe(G) The following Theorem is straightforward from the de?nition of the connected equitable domination. Theorem 2.6 For any graph G with p vertices, 1.

1 ≤ γce(G) ≤ p 2. γce(G) = p if and only if G has p equitable isolated vertices. 3. γce(G) =

1 if there exist at least one vertex v ∈ G, such that dege(v) = p ? 1. Theorem 2.7 For any graph G with δe(G) ≥ 1, p

1 + Δe(G) ≤ γce(G) ≤ 2q ? p + 1. Proof. clearly from the de?nition of the connected equitable dominating set we have γce(G) ≤ p ? 1, then γce(G) ≤ p ?

1 = 2(p ? 1) ? (p ? 1) ≤ 2q ? p + 1. and from Theorem 2.4 we have γ(G) ≤ γe(G) ≤ γce(G) and by Theorem 2.A. we get p 1+Δe(G) ≤ γce(G). Hence p

1 + Δe(G) ≤ γce(G) ≤ 2q ? p +

1 . Theorem 2.8 Let G be a connected graph with p vertices and with out any equitable isolated vertex. Then 1. γce(G) ≤ p ? 1. 2. γce(G) ≤ p ? Δe(G). If G is connected graph and H is any spanning subgraph of G then in general the inequality γe(G) ≤ γe(H) not true similarly the inequality γce(G) ≤ γce(H) is not true in General see the following example H is spanning subgraph of G and γce(G) = γe(G) =

3 but γce(H) = γe(H) = 2.

128 S. Sivakumar, N. D. Soner, Anwar Alwardi and G. Deepak u t u u u u v v u u G H Figure

2 Theorem 2.9 Let G be a connected graph has no non-equitable edge and H is spanning subgraph of H. Then γe(G) ≤ γe(H) Proof. Let G be a connected Graph and let H is the spanning subgraph of H. Suppose That D is the minimum equitable dominating set of H. Then D also equitable dominate all the vertices in V (H) ? D that is D is an equitable dominating set in G. Hence γe(G) ≤ γe(H). A straightforward consequence of Theorem 2.3 is the following. Theorem 2.10 Let G be a connected graph has no non-equitable edge and H is connected spanning subgraph of H. Then γce(G) ≤ γce(H) A vertex of a graph is said to be pendant if its neighborhood contains exactly one vertex. and the vertex which adjacent to the pendent vertex is called support vertex accord........