PDF《Pure Mathematical Sciences, Vol. 1》

Pure Mathematical Sciences, Vol.

1, 2012, no. 3,

123 -

130 Connected Equitable Domination in Graphs S. Sivakumar Department of Studies in Mathematics University of Mysore, Mysore

570 006, India N. D. Soner Department of Studies in Mathematics University of Mysore, Mysore

570 006, India Anwar Alwardi Department of Studies in Mathematics University of Mysore, Mysore

570 006, India a [email protected] G. Deepak Department of Studies in Mathematics University of Mysore, Mysore

570 006, India Abstract Let G = (V, E) be a graph. A subset D of V is called an equitable dominating set of a graph G if for every v ∈ V ?D, there exists a vertex v ∈ D such that uv ∈ E(G) and |deg(u) ? deg(v)| ≤ 1, where deg(u) is the degree of u and deg(v) is the degree of v in G. An equitable dominating set D is said to be a connected equitable dominating set if the subgraph D induced by D is connected. The minimum of the cardinalities of the connected equitable dominating sets of G is called the connected equitable domination number and denoted by γce(G) In this paper we introduce the connected equitable domination and connected equitable domatic in a graph, bounds for γce(G), dce(G) and its exact values for some standard graphs are found. Mathematics Subject Classi?cation: 05C69 Keywords: Connected equitable domination number, Connected equi- table dominating set, Equitable domination number.

124 S. Sivakumar, N. D. Soner, Anwar Alwardi and G. Deepak

1 Introduction By a graph G = (V, E) we mean a ?nite, undirected with neither loops nor multiple edges the order and size of G are denoted by p and q respectively for graph theoretic terminology we refer to Chartrand and Lesnaik [1] A subset S of V is called a dominating set if N[S] = V the minimum (maximum) cardinality of a minimal dominating set of G is called the domination number (upper domination number) of G and is denoted by γ(G), (Γ(G)). An excellent treatment of the fundamentals of domination is given in the book by Haynes etal [3] A survey of several advanced topics in domination is given in the book edited by Haynes et al. [4]. Various types of domination have been de?ned and studied by several authors and more than

75 models of domination are listed in the appendix of Haynes et al. [4]. Sampathkumar and Walikar [6] introduced the concept of connected domination in graphs. Let G = (V, E) be a graph and let v ∈ V the open neighborhood and the closed neighborhood of v are denoted by N(v) and N[v] = N(v) ∪ v respectively. If S ? V then N(S) = ∪v∈SN(v) and N[S] = N(S) ∪ S. If S ? V and u ∈ S then the private neighbor set of u with respect to S is de?ned by Pn[u, S] = {v : N[v] ∩ S = {u}}. A dominating set S of G is called a connected dominating set if the induced subgraph S is connected the minimum cardinality of a connected dominating set of G is called the connected domination number of G and is denoted by γc(G). A subset S of V is called an equitable dominating set if for every v ∈ V ? S there exist a vertex u ∈ S such that uv ∈ E(G) and |deg(u) ? deg(v)| ≤ 1. The minimum cardinality of such an equitable dominating set is denoted by γe(G) and is called the equitable domination number of G. A vertex u is said to be degree equitable with a vertex v ∈ V if |deg(u) ? deg(v)| ≤ 1. If S is an equitable dominating set then any super set of S is an equitable dominating set. An equitable set S is said to be a minimal equitable dominating set if no proper subset of S is an equitable dominating set. If u ∈ V such that |deg(u)?deg(v)| ≥