Open Journal of Discrete Mathematics
Vol.2 No.3(2012), Article ID:21137,3 pages DOI:10.4236/ojdm.2012.23017
The Middle Equitable Dominating Graphs
1Department of Studies in Mathematics, University of Mysore, Mysore, India
2Department of Mathematics, King Abdulaziz University, Jeddah, KSA
Email: aalkenani10@hotmail.com
Received April 20, 2012; revised May 25, 2012; accepted June 15, 2012
Keywords: Eqitable Domination Number; Middle Equitable Dominating Graph; Intersection Graphs
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 Med(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
(a) (b)
Figure 1. Example.
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
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
- K. D. Dharmalingam, “Studies in Graph Theorey-Equitable Domination and Bottleneck Domination,” Ph.D. Thesis, Madurai Kamaraj University, Madurai, 2006.
- F. Harary, “Graph Theory,” Addison-Wesley, Boston, 1969.
- T. W. Haynes, S. T. Hedetniemi and P. J. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, Inc., New York, 1998.
- V. R. Kulli and B. Janakiram, “The Minimal Dominating Graph,” Graph Theory Notes of New York, Vol. 28, Academy of Sciences, New York, 1995, pp. 12-15.
- V. R. Kulli, B. Janakiram and K. M. Niranjan, “The Common Minimal Dominating Graph,” Indian Journal of Pure and Applied Mathematics, Vol. 27, No. 2, 1996, pp. 193- 196.
- V. R. Kulli, B. Janakiram and K. M. Niranjan, “The Vertex Minimal Dominating Graph,” Acta Ciencia Indica, Vol. 28, 2002, pp. 435-440.
- V. R. Kulli, B. Janakiram and K. M. Niranjan, “The Dominating Graph,” Graph Theory Notes of New York, Vol. 46, 2004, pp. 5-8.
- H. B. Walikar, B. D. Acharya and E. Sampathkumar, “Recent Developments in the Theory of Domination in Graphs,” MRI Lecture Notes in Mathematices, Vol. 1, Mehta Research Institute, Alahabad, 1979.