ABSTRACT

Let be a graph and A(G) is the collection of all minimal equitable dominating set of G. The middle equitable dominating graph of G is the graph denoted by M_ed(G) with vertex set the disjoint union of and (u, v) is an edge if and only if whenever or whenever and. In this paper, characterizations are given for graphs whose middle equitable dominating graph is connected and. Other properties of middle equitable dominating graphs are also obtained.

1. Introduction

All the graphs considered here are finite and undirected with no loops and multiple edges. As usual and denote the number of vertices and edges of a graph, respectively. In general, we use to denote the subgraph induced by the set of vertices and and denote the open and closed neighbourhoods of a vertex v, respectively. A set D of vertices in a graph G is a dominating set if every vertex in is adjacent to some vertex in D. The domination number is the minimum cardinality of a dominating set of. For terminology and notations not specifically defined here we refer reader to [1]. For more details about parameters of domination number, we refer to [2], and [3].

A subset D of is called an equitable dominating set of a graph if for every, there exists a vertex such that and . The minimum cardinality of such a dominating set is denoted by and is called equitable domination number of. is minimal if for any vertex, is not a equitable dominating set of. A subset of is called a equitable independent set, if for any, , for all. If a vertex be such that for all then is in each equitable dominating set. Such vertices are called equitable isolates. The equitable neighbourhood of denoted by is defined as and . The cardinality of is denoted by. The maximum and minimum equitable degree of a point in G are denoted respectively by and. That is,. An edge called equitable edge if, for more details about equitable domination number see [4]. Let be a finite set and let be a partition of. Then the intersection graph of is the graph whose vertices are the subsets in and in which two vertices and are adjacent if and only if ,. Kulli and Janakiram introduced new classes of intersection graphs in the field of domination theory see [5-8].

The purpose of this paper is to introduce a new class of intersection graphs in the field of domination theory as follows:

Let be a graph and be the collection of minimal equitable dominating set of. The middle equitable dominating graph of is the graph denoted by with vertex set the disjoint union and is an edge if and only if whenever or whenever and.

Example. Let G be a graph as in Figure 1(a), then the equitable dominating sets are and the The middle equitable dominating graph shown in Figure 1(b).

2. Main Results

Theorem 2.1. A graph with vertices is without equitable edge (equitable edge-free graph) if and only

if.

Proof. Suppose that and if its possible that has equitable edge. Then has at least two minimal equitable dominating set, a contradiction.

Conversely, assume that is equitable edge-free graph with p vertices. Then clear all the vertices are equitable isolated vertices, that is there is only one minimal equitable dominating set contains all the vertices and according the definition of, we get .

Corollary 2.2. If if and only if .

Corollary 2.3. If, where, then.

Corollary 2.4. Let G be complete multi bipartite graph

, where, where, then.

Proposition 2.5. if and only if .

Proof. Suppose that. Then clearly each vertex in will form a minimal equitable dominating set. Hence.

Conversely, suppose and. Then there exists at least one minimal equitable dominating set containing two vertices of. Then will form in.

Proposition 2.6. If, then.

Proof. The proof coming directly from Proposition 2.5.

Theorem 2.7. Let be a graph with p vertices and edges. is a graph with vertices and p edges if and only if.

Proof. If, then that is clear the is a graph with vertices and p edges.

Conversely, let be -graph. Since only the graph is of 2p vertices and p edges, then by Proposition 2.5.

Theorem 2.8. Let be a graph with p vertices and edges. is a graph with vertices and edges if and only if is equitable edge-free graph.

Proof. Let be equitable edge-free graph. Then by Theorem 2.1 is a graph with vertices and edges.

Conversely, let be a graph with vertices and edges that means, and by Theorem 2.1 is equitable edge-free graph.

Theorem 2.9. [1] Let G be a graph, if D is maximal equitable independent set of G, then D also minimal equitable set.

Theorem 2.10. For any graph G with at least two vertices is connected if and only if.

Proof. Let and be any two vertices if there is minimal equitable dominating set containing u and v, the are connected by the path, and if there is no minimal equitable dominating containing both u and v. Then there exists a vertex in such that is neither adjacent to u nor v. Let D and D, be two maximal equitable independent set containing u, w and v, w respectively since every maximal equitable independent set is minimal equitable dominating set by Theorem 2.9, u and v are connected by the path. Thus is connected. Hence is connected.

Conversely, suppose is connected. let and let u be a vertex such that . Then is minimal equitable dominating set and has at least two vertices , it is clear that has no equitable isolated vertices, then containing minimal equitable dominating set say. Since in there is no path joining to any vertex of, this implies that is disconnected, a contradiction. Hence.

Corollary 2.11. Let be a graph and any two vertices in. Then, where is the distance between the vertexand in the graph.

Theorem 2.12. For any graph, if and only if contains one equitable isolated vertex, where is the number of minimal equitable dominating set in.

Proof. If has equitable isolated vertex then the subgraph of which induced by the set of all minimal equitable dominating sets of is complete graph. Hence.

Conversely, Suppose, then it is clear that the vertices of are the minimal equitable dominating sets of. Therefor there exists at least one equitable isolated vertex in.

Theorem 2.13. For any graph, is either connected or it has at least one component which is.

Proof. If, then by Theorem 2.10 is connected, and By Proposition 2.5, if is complete which is connected. Hence we must prove the case.

Let be the set of vertices in such that, where, then it is clear is minimal equitable dominating set. Then each vertex with the minimal equitable dominating set form component isomorphic to. Hence it has at least one component which is.

Theorem 2.14. For any graph with,.

Proof. Let be any graph and. Then by Theorem 2.10, is connected, suppose be any two vertices in, then we have the following cases:

Case 1: Let be any two vertices in. Then by corollary 2.11,.

Case 2: Suppose and be a minimal equitable dominating set in, If then and if then there exists a vertex adjacent to. Hence

and from corollary 2.11 we have. Hence .

Case 3: Suppose that both u and are not in, and u = D, are two minimal equitable dominating sets if D and are adjacent, thensuppose that and are not adjacent then every vertex is adjacent to some vertex and vice versa. Hence Hence.

Theorem 2.15. Let be a graph. Then if and only if or, where is the equitable domatic number of the graph.

Proof. If or, then or G = K_1,2 by Proposition 2.5. Hence. The converse is obvious.

Theorem 2.16. For any graph with at least one equitable isolated vertex,.

Proof. Let be a graph of vertices, and has at least one equitable isolated vertex. Then from the definition of if and any vertices in then and can not be adjacent in, that is there is equitable independent set containing and of size, and this equitable independent will be the maximum equitable independent because is adjacent for all the equitable independent sets. Therefore.

Corollary 2.17. For any graph with at least one equitable isolated vertex, , where is the number of minimal equitable dominating set in

Proof. We have for any graph with vertices, and from [1]. Theorem 3.8.4 corollary is proved.

Theorem 2.18. For any graph, , if and only if is complete graph.

Proof. Let be complete graph. Then from Theorem 2.16, and we have. Hence.

Conversely, suppose. From Theorem 2.16 implies that. Hence.

3. Acknowledgements

The authors wish to thank the referees for their helpful comments.

REFERENCES