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 vertex
and
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, then
suppose 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 = K1,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 ![](https://www.scirp.org/html/3-1200080\8bcde3d1-4afb-44d9-94f2-b05017c83a97.jpg)
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.