# Edge Domination in Some Path and Cycle Related Graphs

Authors: S. K. Vaidya; R. M. Pandit
Journal: ISRN Discrete Mathematics
 (2014)

---

## Abstract

For a graphG
=
V
,
E, a subset F of E is called an edge dominating set of G if every edge not in F is adjacent to some edge in F. The edge domination number γ
′
G of G is the minimum cardinality taken over all edge dominating sets of G. Here, we determine the edge domination number for shadow graphs, middle graphs, and total graphs of paths and cycles.


---

## Body

## 1. Introduction

The domination in graphs is one of the concepts in graph theory which has attracted many researchers to work on it because of its many and varied applications in such fields as linear algebra and optimization, design and analysis of communication networks, and social sciences and military surveillance. Many variants of dominating models are available in the existing literature. For a comprehensive bibliography of papers on the concept of domination, readers are referred to Hedetniemi and Laskar [1]. The present paper is focused on edge domination in graphs.We begin with simple, finite, connected, and undirected graphG
=
(
V
,
E
) of order n. The set S
⊆
V of vertices in a graph G is called a dominating set if every vertex v
∈
V is either an element of S or is adjacent to an element of S. A dominating set S is a minimal dominating set (or MDS) if no proper subset S
′
⊂
S is a dominating set.The minimum cardinality of a dominating set ofG is called the domination number of G which is denoted by γ
(
G
), and the corresponding dominating set is called a γ-set of G.The open neighborhoodN
(
v
) of v
∈
V is the set of vertices adjacent to v, and the set N
[
v
]
=
N
(
v
)
∪
{
v
} is the closed neighborhood of v.For any real numbern, ⌈
n
⌉ denotes the smallest integer not less than n and ⌊
n
⌋ denotes the greatest integer not greater than n.An edgee of a graph G is said to be incident with the vertex v if v is an end vertex of e. In this case, we also say that v is incident with e. Two edges e and f which are incident with a common vertex v are said to be adjacent.In a graphG, a vertex of degree one is called a pendant vertex, and an edge incident with a pendant vertex is called a pendant edge.A subsetF
⊆
E is an edge dominating set if each edge in E is either in F or is adjacent to an edge in F. An edge dominating set F is called a minimal edge dominating set (or MEDS) if no proper subset F
′ of F is an edge dominating set. The edge domination number γ
′
(
G
) is the minimum cardinality among all minimal edge dominating sets. The concept of edge domination was introduced by Mitchell and Hedetniemi [2] and it is explored by many researchers. Arumugam and Velammal [3] have discussed the edge domination in graphs while the fractional edge domination in graphs is discussed in Arumugam and Jerry [4]. The complementary edge domination in graphs is studied by Kulli and Soner [5] while Jayaram [6] has studied the line dominating sets and obtained bounds for the line domination number. The bipartite graphs with equal edge domination number and maximum matching cardinality are characterized by Dutton and Klostermeyer [7] while Yannakakis and Gavril [8] have shown that edge dominating set problem is NP-complete even when restricted to planar or bipartite graphs of maximum degree 3. The independent edge dominating sets of certain graphs are discussed in Mojdeh and Sadeghi [9] while a constructive characterization for trees with equal edge domination and end edge domination numbers is investigated by Muddebihal and Sedamkar [10]. The edge domination in graphs of cubes is studied by Zelinka [11].Throughout the paper,P
n and C
n will denote the path and the cycle with n vertices, respectively.We will give brief summary of definitions which are useful for the present investigations.Definition 1.
The open neighborhood of an edgee
∈
E is denoted as N
(
e
) and it is the set of all edges adjacent to e in G. Further, N
[
e
]
=
N
(
e
)
∪
{
e
} is the closed neighborhood of e in G.Definition 2.
The degree of an edgee
=
u
v of G is defined by deg
⁡
(
e
)
=
deg
⁡
(
u
)
+
deg
⁡
(
v
)
-
2 and it is equal to the number of edges adjacent to it. The maximum degree of an edge in G is denoted by Δ
′
(
G
).Definition 3 (see [12]).
The line graph ofG, written L
(
G
), is the simple graph whose vertices are the edges of G, with e
f
∈
E
(
L
(
G
)
) when e and f have a common end vertex in G.Definition 4 (see [13]).
The shadow graph of a connected graphG is constructed by taking two copies of G, say, G
′ and G
′′. Join each vertex u
′ of G
′ to the neighbors of the corresponding vertex u
′′ of G
′′. The shadow graph of G is denoted by D
2
(
G
).Definition 5 (see [13]).
The middle graph of a connected graphG denoted by M
(
G
) is the graph whose vertex set is V
(
G
)
∪
E
(
G
) where two vertices are adjacent if(i)
they are adjacent edges ofG, or
(ii)
one is a vertex ofG and the other is an edge incident with it.Definition 6 (see [14]).
The total graph ofG denoted by T
(
G
) is the graph whose vertex set is V
(
G
)
∪
E
(
G
) and two vertices are adjacent in T
(
G
) if(i)
they are adjacent edges ofG, or
(ii)
one is a vertex ofG and the other is an edge incident with it, or
(iii)
they are adjacent vertices ofG.
It is easy to see thatT
(
G
) always contains both G and the line graph L
(
G
) as its induced subgraph. The total graph is the largest graph that is formed by the adjacency relations of elements of a graph.
For the various graph theoretic notations and terminology, we follow West [12] while the terms related to the concept of domination are used in the sense of Haynes et al. [15].
Generally, the following types of problems are considered in the field of domination in graphs:(1)
to introduce new types of dominating models,
(2)
to determine bounds in terms of various graph parameters,
(3)
to obtain the exact domination number for some graphs or graph families,
(4)
to study the algorithmic and complexity results for particular dominating parameters, and
(5)
to characterize the graphs with certain dominating parameters.
The present work is intended to discuss the problem of the third kind in the context of edge domination in graphs. In this paper, we investigate the edge domination number of middle graphs, total graphs, and shadow graphs ofP
n and C
n.


## 2. Main Results

Theorem 7.
γ
′
(
D
2
(
P
n
)
)
=
2
⌈
(
n
-
1
)
/
3
⌉.Proof.
Consider two copies ofP
n. Let v
1
,
v
2
,
…
,
v
n be the vertices of the first copy of P
n and let u
1
,
u
2
,
…
,
u
n be the vertices of the second copy of P
n. Let e
1
,
e
2
,
…
,
e
n
-
1 be the edges of the first copy of P
n and let e
1
′
,
e
2
′
,
…
,
e
n
-
1
′ be the edges of the second copy of P
n where e
i connects v
i and v
i
+
1 and e
i
′ connects u
i and u
i
+
1. Then |
V
(
D
2
(
P
n
)
)
|
=
2
n and |
E
(
D
2
(
P
n
)
)
|
=
4
(
n
-
1
).
Forn
≤
4, F
1
=
{
e
n
-
1
,
e
n
-
1
′
} is obviously an MEDS with minimum cardinality among all minimal edge dominating sets of D
2
(
P
n
). Hence, γ
′
(
D
2
(
P
n
)
)
=
2
=
2
⌈
(
n
-
1
)
/
3
⌉.
Forn
>
4, we construct an edge set of D
2
(
P
n
) as follows:
(1)
F
=
{
{
e
2
,
e
2
′
,
e
5
,
e
5
′
,
…
,
e
3
i
+
2
,
e
3
i
+
2
′
}
if
n
≡
0
or
1
(
mod
⁡
3
)
{
e
2
,
e
2
′
,
e
5
,
e
5
′
,
…
,
e
3
i
+
2
,
e
3
i
+
2
′
}
∪
{
e
n
-
1
,
e
n
-
1
′
}
if
n
≡
2
(
mod
⁡
3
)
,
where 0
≤
i
≤
⌈
(
n
-
5
)
/
3
⌉ with |
F
|
=
2
⌈
(
n
-
1
)
/
3
⌉.
Since each edge inE
(
D
2
(
P
n
)
) is either in F or is adjacent to an edge in F, it follows that the above set F is an edge dominating set of D
2
(
P
n
).
Moreover, the above setF is an MEDS of D
2
(
P
n
) because for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of D
2
(
P
n
). Now, deg
⁡
(
e
3
i
+
2
)
=
6
=
deg
⁡
(
e
3
i
+
2
′
)
=
Δ
′
(
D
2
(
P
n
)
) for 0
≤
i
≤
⌈
(
n
-
5
)
/
3
⌉ and deg
⁡
(
e
n
-
1
)
=
4
=
deg
⁡
(
e
n
-
1
′
)
=
Δ
′
(
D
2
(
P
n
)
)
-
2 and pairs of edges {
e
3
i
+
2
,
e
3
i
+
2
′
} for 0
≤
i
≤
⌈
(
n
-
5
)
/
3
⌉ will dominate maximum number of distinct edges of D
2
(
P
n
). Therefore, any set containing the edges less than that of F cannot be an edge dominating set of D
2
(
P
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of D
2
(
P
n
).
Thus,γ
′
(
D
2
(
P
n
)
)
=
2
⌈
(
n
-
1
)
/
3
⌉.Theorem 8.
γ
′
(
M
(
P
n
)
)
=
⌊
n
/
2
⌋.Proof.
Letv
1
,
v
2
,
…
,
v
n be the vertices of path P
n and let u
1
,
u
2
,
…
,
u
n
-
1 be the added vertices corresponding to the edges f
1
,
f
2
,
…
,
f
n
-
1 of P
n to obtain M
(
P
n
). Thus, V
(
M
(
P
n
)
)
=
{
v
1
,
v
2
,
…
,
v
n
,
f
1
,
f
2
,
…
,
f
n
-
1
}.
Then|
V
(
M
(
P
n
)
)
|
=
2
n
-
1 and |
E
(
M
(
P
n
)
)
|
=
3
n
-
4. Let the edges e
1
,
e
2
,
…
,
e
n
-
2
∈
E
(
M
(
P
n
)
) where e
k
=
u
k
u
k
+
1.
Now, the edge setsF
=
{
v
1
u
1
} and F
=
{
u
1
u
2
} are clearly the minimal edge dominating sets of M
(
P
2
) and M
(
P
3
), respectively, with minimum cardinality among all minimal edge dominating sets of M
(
P
n
). Hence, γ
′
(
M
(
P
n
)
)
=
1
=
⌊
n
/
2
⌋ for n
=
2,3.
Forn
≥
4, we construct an edge set of M
(
P
n
) as follows:
(2)
F
=
{
e
1
,
e
3
,
…
,
e
2
i
+
1
}
∪
{
e
n
-
2
}
hh
for
0
≤
i
≤
⌊
n
-
4
2
⌋
hhhhhhhhhhhhhhhhhhhhhhhhlhhl
with
|
F
|
=
⌊
n
2
⌋
.
Since each edge inE
(
M
(
P
n
)
) is either in F or is adjacent to an edge in F, it follows that the above set F is an edge dominating set of M
(
P
n
). Moreover, the above set F is an MEDS of M
(
P
n
) because for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of M
(
P
n
).
Now, each graphM
(
P
n
), for n
≥
4, has two nonadjacent pendant edges and there is no edge which is adjacent to both pendant edges. Hence, at least two distinct edges are required to dominate these pendant edges. Moreover, deg
⁡
(
e
i
)
=
6
=
Δ
′
(
M
(
P
n
)
) for 1
<
i
<
n
-
2 and for n
≥
5; each edge of at most ⌊
(
n
-
2
)
/
3
⌋ distinct edges out of total 3
n
-
4 edges of M
(
P
n
) can dominate seven distinct edges of M
(
P
n
) including itself and each of the remaining edges can dominate less than six distinct edges of M
(
P
n
) at a time. Therefore, any set containing edges less than that of F cannot be an edge dominating set of M
(
P
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of M
(
P
n
).
Thus,γ
′
(
M
(
P
n
)
)
=
⌊
n
/
2
⌋.Theorem 9.
For pathP
n,
(3)
γ
′
(
T
(
P
n
)
)
=
{
⌈
2
n
-
1
3
⌉
i
f
n
≡
0
o
r
2
(
mod
⁡
3
)
⌊
2
n
-
1
3
⌋
o
t
h
e
r
w
i
s
e
.Proof.
Letv
1
,
v
2
,
…
,
v
n be the vertices of path P
n and let u
1
,
u
2
,
…
,
u
n
-
1 be the added vertices corresponding to the edges e
1
,
e
2
,
…
,
e
n
-
1 of P
n to obtain T
(
P
n
). Thus, V
(
T
(
P
n
)
)
=
{
v
1
,
v
2
,
…
,
v
n
,
u
1
,
u
2
,
…
,
u
n
-
1
}. The graph T
(
P
n
) will have (
2
n
-
1
) vertices and (
4
n
-
5
) edges. Let the edges f
1
,
f
2
,
…
,
f
2
(
n
-
1
)
∈
E
(
T
(
P
n
)
) where f
i
=
u
⌈
i
/
2
⌉
v
⌈
i
/
2
⌉ for odd i and f
i
=
u
i
/
2
v
(
i
/
2
)
+
1 for even i.
Now, we construct the edge sets ofT
(
P
n
) as follows:
(4)
F
=
{
{
f
2
,
f
5
,
…
,
f
3
j
+
2
}
if
n
≡
2
(
mod
⁡
3
)
{
f
2
,
f
5
,
…
,
f
3
j
+
2
}
∪
{
f
2
(
n
-
1
)
}
if
n
≡
0
(
mod
⁡
3
)
,
for 0
≤
j
≤
2
⌈
(
n
-
3
)
/
3
⌉ with |
F
|
=
⌈
(
2
n
-
1
)
/
3
⌉, and F
=
{
f
2
,
f
5
,
…
,
f
3
k
+
2
} if n
≡
1
(
mod
⁡
3
), for 0
≤
k
≤
⌊
(
2
n
-
3
)
/
3
⌋ with |
F
|
=
⌊
(
2
n
-
1
)
/
3
⌋.
The above setF is an edge dominating set of T
(
P
n
) because each edge in E
(
T
(
P
n
)
) is either in F or is adjacent to an edge in F. Also, since for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of T
(
P
n
), it follows that the above set F is an MEDS of T
(
P
n
).
Now, the setsF
=
{
f
2
} and F
=
{
f
2
,
f
4
} are clearly minimal edge dominating sets of T
(
P
2
) and T
(
P
3
) respectively with minimum cardinality. Hence, γ
′
(
T
(
P
2
)
)
=
1 and γ
′
(
T
(
P
3
)
)
=
2. For n
>
3, Δ
′
(
T
(
P
n
)
)
=
6 implying that an edge of T
(
P
n
) can dominate at most seven distinct edges of T
(
P
n
) including itself. But, from the nature of graph, we can observe that each of at most ⌊
(
n
-
2
)
/
2
⌋ distinct edges of T
(
P
n
) can dominate seven distinct edges including itself and each of the remaining edges can dominate less than six edges of T
(
P
n
). Therefore, any set containing the edges less than that of F cannot be an edge dominating set of T
(
P
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of T
(
P
n
).
This implies that(5)
γ
′
(
T
(
P
n
)
)
=
{
⌈
2
n
-
1
3
⌉
if
n
≡
0
or
2
(
mod
⁡
3
)
⌊
2
n
-
1
3
⌋
otherwise
.Theorem 10.
For cycleC
n,
(6)
γ
′
(
D
2
(
C
n
)
)
=
{
2
⌈
n
-
1
3
⌉
i
f
n
≡
0
o
r
2
(
mod
⁡
3
)
2
⌈
n
+
1
3
⌉
o
t
h
e
r
w
i
s
e
.Proof.
Consider two copies ofC
n. Let v
1
,
v
2
,
…
,
v
n be the vertices of the first copy of C
n and let u
1
,
u
2
,
…
,
u
n be the vertices of the second copy of C
n. Let e
1
,
e
2
,
…
,
e
n be the edges of the first copy of C
n and e
1
′
,
e
2
′
,
…
,
e
n
′ be the edges of the second copy of C
n. Then |
V
(
D
2
(
C
n
)
)
|
=
2
n and |
E
(
D
2
(
C
n
)
)
|
=
4
n
-
1.
First, we construct an edge set ofD
2
(
C
n
) as follows:
(7)
F
=
{
{
e
2
,
e
5
,
…
,
e
3
i
+
2
,
e
2
′
,
e
5
′
,
…
,
e
3
i
+
2
′
}
if
n
≡
0
or
2
(
mod
⁡
3
)
{
e
2
,
e
5
,
…
,
e
3
i
+
2
,
e
2
′
,
e
5
′
,
…
,
e
3
i
+
2
′
}
∪
{
e
n
,
e
n
′
}
otherwise
,
hhhhhhhhhhhhhhhhhhhl
where
0
≤
i
≤
⌊
n
-
2
3
⌋
with |
F
|
=
2
⌈
(
n
-
1
)
/
3
⌉ for n
≡
0 or 2
(
mod
⁡
3
) and |
F
|
=
2
⌈
(
n
+
1
)
/
3
⌉ for n
≡
1
(
mod
⁡
3
).
Since each edge inE
(
D
2
(
C
n
)
) is either in F or is adjacent to an edge in F, it follows that the above set F is an edge dominating set of D
2
(
C
n
).
Now, the above set is an MEDS ofD
2
(
C
n
) because for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of D
2
(
C
n
). Moreover, deg
⁡
(
e
i
)
=
6
=
deg
⁡
(
e
i
′
)
=
Δ
′
(
D
2
(
C
n
)
) for 1
≤
i
≤
n and each edge of D
2
(
C
n
) can dominate at most seven distinct edges of D
2
(
C
n
) including itself. But, at a time, each of at most ⌈
(
n
-
2
)
/
3
⌉ distinct edges of D
2
(
C
n
) can dominate seven distinct edges of D
2
(
C
n
) including itself and each of the remaining edges can dominate less than six distinct edges of D
2
(
C
n
). Therefore, any set containing the edges less than that of F cannot be an edge dominating set of D
2
(
C
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of D
2
(
C
n
).
Thus,(8)
γ
′
(
D
2
(
C
n
)
)
=
{
2
⌈
n
-
1
3
⌉
if
n
≡
0
or
2
(
mod
⁡
3
)
2
⌈
n
+
1
3
⌉
otherwise
.Theorem 11.
γ
′
(
M
(
C
n
)
)
=
⌊
(
n
+
1
)
/
2
⌋.Proof.
Letv
1
,
v
2
,
…
,
v
n be the vertices of cycle C
n and let u
1
,
u
2
,
…
,
u
n be the added vertices corresponding to the edges f
1
,
f
2
,
…
,
f
n of C
n to obtain M
(
C
n
). Then |
V
(
M
(
C
n
)
)
|
=
2
n and |
E
(
M
(
C
n
)
)
|
=
3
n. Let the edges e
1
,
e
2
,
…
,
e
n
∈
E
(
M
(
C
n
)
), where e
k
=
u
k
u
k
+
1.
Now, we construct an edge set ofM
(
C
n
) as follows:
(9)
F
=
{
e
2
,
e
4
,
…
,
e
2
i
}
∪
{
e
n
}
for
1
≤
i
≤
⌊
n
-
1
2
⌋
hhhhhhhhhhhhhhhhhhlhhl
with
|
F
|
=
⌊
n
+
1
2
⌋
.
Since each edge inE
(
M
(
C
n
)
) is either in F or is adjacent to an edge in F, it follows that the above set F is an edge dominating set of M
(
C
n
). Moreover, the above set F is an MEDS of M
(
C
n
) because for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of M
(
C
n
).
Now,deg
⁡
(
e
i
)
=
6
=
Δ
′
(
M
(
C
n
)
) for 1
≤
i
≤
n and each edge of M
(
C
n
) can dominate at most seven distinct edges of M
(
C
n
) including itself. But, at a time, each of at most ⌊
(
n
-
2
)
/
3
⌋ edges of M
(
C
n
) can dominate seven distinct edges of M
(
C
n
) including itself and each of the remaining edges can dominate less than six distinct edges of M
(
C
n
). Therefore, any set containing the edges less than that of F cannot be an edge dominating set of M
(
C
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of M
(
C
n
).
Thus,γ
′
(
M
(
C
n
)
)
=
⌊
(
n
+
1
)
/
2
⌋.Theorem 12.
For cycleC
n
(10)
γ
′
(
T
(
C
n
)
)
=
{
⌈
2
n
-
1
3
⌉
i
f
n
≡
0
o
r
1
(
mod
⁡
3
)
⌈
2
n
+
1
3
⌉
o
t
h
e
r
w
i
s
e
.Proof.
Letv
1
,
v
2
,
…
,
v
n be the vertices of cycle C
n and let u
1
,
u
2
,
…
,
u
n be the added vertices corresponding to the edges e
1
,
e
2
,
…
,
e
n of C
n to obtain T
(
C
n
). Then |
V
(
T
(
C
n
)
)
|
=
2
n and |
E
(
T
(
C
n
)
)
|
=
4
n. Let the edges f
1
,
f
2
,
…
,
f
2
n
∈
E
(
T
(
C
n
)
) where f
k
=
u
⌈
k
/
2
⌉
v
⌈
k
/
2
⌉ for odd k and f
k
=
u
(
k
/
2
)
v
(
k
/
2
)
+
1 for even k.
First, we construct an edge set ofT
(
C
n
) as follows:
(11)
F
=
{
{
f
2
,
f
5
,
…
,
f
3
i
+
2
}
if
n
≡
0
or
1
(
mod
⁡
3
)
{
f
2
,
f
5
,
…
,
f
3
i
+
2
}
∪
{
f
2
n
}
otherwise
,
for 0
≤
i
≤
⌈
(
2
n
-
4
)
/
3
⌉, with |
F
|
=
⌈
(
2
n
-
1
)
/
3
⌉ if n
≡
0
or
1
(
mod
⁡
3
) and |
F
|
=
⌈
(
2
n
+
1
)
/
3
⌉ if n
≡
2
(
mod
⁡
3
).
The above setF is an edge dominating set of T
(
C
n
) because each edge in E
(
T
(
C
n
)
) is either in F or is adjacent to an edge in F. Since for any edge e
∈
F, the set F
-
{
e
} does not dominate the edges in N
(
e
) of T
(
C
n
), it follows that the above set F is an MEDS of T
(
C
n
).
Now,deg
⁡
(
f
i
)
=
6
=
Δ
′
(
T
(
C
n
)
) for 1
≤
i
≤
2
n and each edge of T
(
C
n
) can dominate at most seven distinct edges of T
(
C
n
) including itself. But, at a time, each of at most ⌊
n
/
2
⌋ distinct edges of T
(
C
n
) can dominate seven distinct edges of T
(
C
n
) including itself and each of the remaining edges can dominate less than six distinct edges of T
(
C
n
). Therefore, any set containing the edges less than that of F cannot be an edge dominating set of T
(
C
n
). This implies that the above edge dominating set F is of minimum cardinality.
Hence, the above setF is an MEDS with minimum cardinality among all minimal edge dominating sets of T
(
C
n
).
Thus,(12)
γ
′
(
T
(
C
n
)
)
=
{
⌈
2
n
-
1
3
⌉
if
n
≡
0
or
1
(
mod
⁡
3
)
⌈
2
n
+
1
3
⌉
otherwise
.


## 3. Concluding Remarks

Here, we have taken up a problem to determine the edge domination number for the larger graphs obtained by means of three graph operations on paths and cycles. To derive similar results in the context of other variants of domination is an open area of research.



---

*Source: 975812-2014-03-13.xml*