Open Journal of Discrete Mathematics
Vol.2 No.3(2012), Article ID:21130,3 pages DOI:10.4236/ojdm.2012.23018
Some New Results on Domination Integrity of Graphs
1Saurashtra University, Rajkot, India
2B. H. Gardi College of Engineering & Technology, Rajkot, India
Email: samirkvaidya@yahoo.co.in, nirang_kothari@yahoo.com
Received April 10, 2012; revised May 15, 2012; accepted May 30, 2012
Keywords: Integrity; Dominating Set; Domination Integrity
ABSTRACT
The domination integrity of a connected graph 
is denoted as 
and defined by 
= 
where 
is the order of a maximum component of
. We discuss domination integrity in the context of some graph operations like duplication of an edge by vertex and duplication of vertex by an edge.
1. Introduction
The vulnerability of communication network measures the resistance of network to the disruption of operation after the failure of certain station or communication links. For any communication network greater degrees of stability or less vulnerability is required. Vulnerability can be measured by certain parameters like connectivity, toughness, integrity, binding number etc. In the analysis of vulnerability of communication network to disruption, following two parameters are of great importance: 1) The size of the largest remaining group within which mutual communication can still occur; 2) The number of elements that are not functioning. In this context Barefoot et al. [1] have introduced the concept of integrity of a graph as a new measure of vulnerability of network.
Definition 1.1. The integrity of a graph G is denoted by 
and defined by 
where m(G – S) is the order of a maximum component of 
Definition 1.2. An I-set of G is any (proper) subset S of 
for which 
The connectedness of graph is not essential to define integrity. The integrity of middle graphs is discussed by Mamut and Vumar [2] while integrity of total graphs is discussed by Dundar and Aytac [3]. If D is any minimal dominating set and if the order of the largest component of G – D is small then the removal of D will crash the communication network. The decision making process as well as communication between remaining members will also be highly affected. Considering this aspect Sundareswaran and Swaminathan [4] introduced the concept of domination integrity which is defined as follows.
Definition 1.3. The domination integrity of a connected graph G is denoted as 
and defined by 
where 
is the order of a maximum component of
.
Sundareswarn and Swaminathan [5] have investigated domination integrity of middle graph of some graphs. In the present work, we investigate the domination integrity for the graphs obtained by various graph operations. In other words we have tried to relate expansion of network with measure of vulnerability.
Definition 1.4. Duplication of a vertex 
by a new edge 
in graph G produces a new graph 
such that 
and
.
Definition 1.5. Duplication of an edge 
by a new vertex 
in a graph G produces a new graph 
such that 
Definition 1.6. For the dominating set 
a vertex 
is called isolate of 
if 
For all other standard terminology and graph theoretical notation we refer to Hynes et al. [6].
2. Main Results
Lemma 2.1. Let G be a graph obtained by duplication of each edge by vertex of path 
then 
Proof: Let G be a graph obtained by duplicating each edge 
of path 
by vertex 
There are three types of vertices in G
1) 
2) 
for 
and
3) 
It is obvious that 
must be in the dominating set as they are the most dominating vertices. From the nature of the graph G it is obvious that out of the vertices 
and 
at least one vertex must belongs to any dominating set S as 
is adjacent to only 
and 
Therefore if S is any dominating set then 
We claim that 
when n is even and 
when 
is odd are minimal dominating sets.
One can observe that each 
and 
are adjacent to v2i and removal of 
from set S, 
will not be dominated by any vertex of S Hence 
Theorem 2.2. Let G be a graph obtained by duplication of each edge by vertex of path 
then
Proof: To prove the result, we consider following three cases.
Case-1. When
: Let G be a graph obtained by duplication of an edge 
of path 
by a vertex 
Then 
and 
as a γ-set of G and then 
This implies 
If 
is any dominating set with 
then 
and consequently 
Hence in all the cases 
Case-2. When
: Let G be a graph obtained by duplication of an edge v1v2 and v2v3 of path 
by the vertices u1 and u3 respectively. As 
is the only γ-set of G then 
and m(G – D) = 2. If S1 is any dominating set with 
then 
and
. If S2 is any dominating set with 
then 
and 
Moreover 
is not possible, as the order of the largest component of 
is at most 3. Thus
.
Case-3. When
: Let G be a graph obtained by duplication of an edge 
of path 
by vertex 
Then 
with 
is a γ- set of 
and 
Consequently
If 
is any dominating set with
then 
and
If 
is any dominating set with 
then 
and 
Hence we have
.
Theorem 2.3. Let 
be a graph obtained by duplication of each edge by vertex of path 
then
(if
)
Proof: Let G be a graph obtained by duplicating each edge vivi+1 of path Pn by vertex 
where 
Then from Theorem 2.1 
If n is even then 
is a γ-set of G otherwise 
is a γ-set of G Therefore 
which implies,
(1)
We will show that the number 
is minimum. For that we have to take into account the minimality of both 
and
. The minimality of 
is guaranteed as S is γ-set. Now it remains to show that if S is any dominating set other than D then 
If 
then 
and 
If 
then 
which implies that
If 
then trivially
Hence for any dominating set S
(2)
From (1) and (2) we have 
(if n ≥ 5).
Theorem 2.4. Let 
be a graph obtained by duplication of each vertex by an edge of path 
or cycle 
then 
Proof: Let 
be a graph obtained by duplication of vertices 
of path 
or cycle 
by an edge 
Then from the construction of graph G it is obvious that from the vertices 
and 
at least one vertex must belong to any dominating set 
Consequently if 
is any dominating set then 
We claim that set 
is a minimal dominating set. Because each 
is adjacent to 
and 
If 
is removed from set 
then 
and 
will not be dominated by any vertex. Thus 
is a minimal dominating set with minimum cardinality. Hence 
Theorem 2.5. Let 
be a graph obtained by duplication of each vertex of path 
or cycle 
by an edge then 
Proof: Let 
be a graph obtained by duplication of each vertex 
of path 
or cycle 
by an edge 
Then from Theorem 2.4 we have 
Let 
be a γ-set of graph G. Then 
Therefore,
(1)
We will show that the number 
is minimum. For that we have to take into account the minimality of both 
and 
The minimality of 
is guaranteed as S is γ-set. Now it remains to show that if S is any dominating set other than D then 
. If 
then
, consequently 
If 
then trivially 
Hence for any dominating set S,
(2)
From (1) and (2) we have 
Proposition 2.6 [6]. A dominating set 
is a minimal dominating set if and only if for each vertex
, one of the following two conditions holds:
1) u is an isolate of
.
2) There exists a vertex 
for which 
Lemma 2.7. Let G be a graph obtained by duplication of each vertex of wheel 
by an edge then 
Proof: Let 
be a graph obtained by duplication of rim vertices as well as apex vertex altogether of wheel 
by edges
and 
respectively. Then each rim vertex 
will dominate the vertices 
and apex vertex 
For 
there exists a vertex 
such that 
is a singleton set. Then from Proposition 2.6 
will be a minimal dominating set of 
If 
is any dominating set then we claim that 
Because
1) If all the elements of 
are only of the type 
then 
2) If elements of 
are combination of 
and 
then 
3) If 
contains any of first two types together with the apex vertex then 
4) If 
contains 
and apex vertex then 
Thus we have 
Theorem 2.8. Let 
be a graph obtained by duplication of each vertex of wheel 
by an edge then 
Proof: Let 
be a graph obtained by duplication of apex vertex 
of wheel 
by an edge 
and the rim vertices 
of wheel 
by an edge 
Then from Lemma 2.7 we have 
Let 
be a γ-set of graph G. Then 
Therefore
(1)
We will show that the number 
is minimum. For that we have to take into account the minimality of both 
and 
The minimality of 
is guaranteed as S is γ-set. Now it remains to show that if S is any dominating set other than D then
If 
then
consequently
If 
then 
consequently
If 
then trivially 
Thus for any dominating set S,
(2)
Hence from (1) and (2) 
3. Concluding Remarks
We have investigated domination integrity of three special graph families. This work relates to network expansion and measure of vulnerability. We conclude that expansion of network will provide the reason for increase of vulnerability. To investigate similar results for different graph families obtained by various graph operations is an open area of research.
4. Acknowledgements
The authors are highly thankful to the anonymous referee for valuable comments and constructive suggestions.
REFERENCES
- C. A. Barefoot, R. Entringer and H. C. Swart, “Vulnerability in Graphs—A Comparative Survey,” Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 1, 1987, pp. 13-22.
- A. Mamut and E. Vumar, “A Note on the Integrity of Middle Graphs,” Lecture Notes in Computer Science, Vol. 4381, 2007, pp. 130-134.
- P. Dundar and A. Aytac, “Integrity of Total Graphs via Certain Parameters,” Mathematical Notes, Vol. 75, No. 5, 2004, pp. 665-672.
- R. Sundareswaran and V. Swaminathan, “Domination Integrity in Graphs,” Proceedings of International Conference on Mathematical and Experimental Physics, Prague, 3-8 August 2009, pp. 46-57.
- R. Sundareswaran and V. Swaminathan, “Domination Integrity of Middle Graphs,” In: T. Chelvam, S. Somasundaram and R. Kala, Eds., Algebra, Graph Theory and Their Applications, Narosa Publishing House, New Delhi, 2010, pp. 88-92.
- T. Haynes, S. Hedetniemi and P. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, Inc., New York, 1998.