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 ![](https://www.scirp.org/html/4-1200076\be9554d1-5e78-42c5-a225-527eada1054c.jpg)
Definition 1.2. An I-set of G is any (proper) subset S of
for which ![](https://www.scirp.org/html/4-1200076\6b95fe83-9c9e-4229-ad3b-ac203c371d47.jpg)
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 ![](https://www.scirp.org/html/4-1200076\d140648f-b573-4e1a-963f-21dbba6d20b3.jpg)
Definition 1.6. For the dominating set
a vertex
is called isolate of
if ![](https://www.scirp.org/html/4-1200076\31619bc6-67e3-42dd-b1be-a39f4edc322e.jpg)
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 ![](https://www.scirp.org/html/4-1200076\b9d15223-8de5-46cd-8c16-dbb4d5536c5a.jpg)
Proof: Let G be a graph obtained by duplicating each edge
of path
by vertex
There are three types of vertices in G
1) ![](https://www.scirp.org/html/4-1200076\ed13c862-6410-47ff-95b9-ac6eab6e621f.jpg)
2)
for
and
3) ![](https://www.scirp.org/html/4-1200076\94acb46b-bbce-47ed-98f8-66f1bff7ff40.jpg)
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 ![](https://www.scirp.org/html/4-1200076\fd45cdd3-8f9e-4cbb-935c-bbf408854fad.jpg)
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 ![](https://www.scirp.org/html/4-1200076\7ea71702-780e-44ce-8cc8-204319091bc5.jpg)
Theorem 2.2. Let G be a graph obtained by duplication of each edge by vertex of path
then
![](https://www.scirp.org/html/4-1200076\50b6e746-8311-4623-854d-cdf206c25919.jpg)
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 ![](https://www.scirp.org/html/4-1200076\8762af7f-8eb5-47c7-b8cf-914317b4fbb9.jpg)
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 ![](https://www.scirp.org/html/4-1200076\5e0da8ff-160a-48bf-bbd8-d010cb9a7cd5.jpg)
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 ![](https://www.scirp.org/html/4-1200076\2ef9b913-3318-4324-85a0-d29367745663.jpg)
If
then ![](https://www.scirp.org/html/4-1200076\18e7c4df-bc0a-4c87-8a18-e1c02c101395.jpg)
and ![](https://www.scirp.org/html/4-1200076\d50cb22f-c039-4159-96dc-02d51c003852.jpg)
If
then ![](https://www.scirp.org/html/4-1200076\0c0d0dba-4090-4139-801b-f2a429b40177.jpg)
which implies that
![](https://www.scirp.org/html/4-1200076\9e45fedd-ab20-4ac9-ae0d-7638598c9b19.jpg)
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 ![](https://www.scirp.org/html/4-1200076\9bf53a00-568b-4954-bdb8-647a3cc9312a.jpg)
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 ![](https://www.scirp.org/html/4-1200076\7096b76c-3cc2-4d48-aa4c-602e8e51c487.jpg)
Theorem 2.5. Let
be a graph obtained by duplication of each vertex of path
or cycle
by an edge then ![](https://www.scirp.org/html/4-1200076\3f939a89-6c57-4b7e-a173-2ff4ace1ad86.jpg)
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 ![](https://www.scirp.org/html/4-1200076\9b565a02-c01a-43e5-87ba-7a8549c7bfb0.jpg)
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 ![](https://www.scirp.org/html/4-1200076\83ace0ea-d6bf-45eb-96a9-80ea073c2486.jpg)
Lemma 2.7. Let G be a graph obtained by duplication of each vertex of wheel
by an edge then ![](https://www.scirp.org/html/4-1200076\3070dc36-c25e-47f4-a851-2dd57eb8de6f.jpg)
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 ![](https://www.scirp.org/html/4-1200076\6454bb3d-dab8-4d16-a154-af39909bb45b.jpg)
2) If elements of
are combination of
and
then ![](https://www.scirp.org/html/4-1200076\e48c10b7-1574-40ca-8d65-f545e52b3343.jpg)
3) If
contains any of first two types together with the apex vertex then ![](https://www.scirp.org/html/4-1200076\00e2acd6-42ba-4ccd-9fb4-a71eddb9871a.jpg)
4) If
contains
and apex vertex then ![](https://www.scirp.org/html/4-1200076\52f9ca33-c996-4df2-be2b-0153b94936ba.jpg)
Thus we have ![](https://www.scirp.org/html/4-1200076\9919e689-f975-4da9-ae45-f442f7372d33.jpg)
Theorem 2.8. Let
be a graph obtained by duplication of each vertex of wheel
by an edge then ![](https://www.scirp.org/html/4-1200076\ec380289-7f78-434a-b49f-86d12007414b.jpg)
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
![](https://www.scirp.org/html/4-1200076\3d4bfd62-064e-480e-925d-c3a0fade55dd.jpg)
If
then
consequently
![](https://www.scirp.org/html/4-1200076\17c08b82-9f74-449f-a75b-56636d005460.jpg)
If
then
consequently
![](https://www.scirp.org/html/4-1200076\b6642434-f68d-4f96-8d66-e6d06fdd545e.jpg)
If
then trivially
Thus for any dominating set S,
(2)
Hence from (1) and (2) ![](https://www.scirp.org/html/4-1200076\cce3368e-6576-4071-a233-0abcec06dbea.jpg)
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.