See discussions, stats, and author profiles for this publication at: [Link]

net/publication/360087778

A STUDY ON EDGE DOMINATION THEORY IN GRAPH

Article · April 2022

CITATIONS READS

2 792

1 author:

Venugeetha Y.
Don Bosco Institute of Technology, Bengaluru, India
17 PUBLICATIONS 7 CITATIONS

SEE PROFILE

All content following this page was uploaded by Venugeetha Y. on 21 April 2022.

The user has requested enhancement of the downloaded file.

 A STUDY ON EDGE DOMINATION THEORY IN GRAPH
[Link] Y*, Prof. V R Kulli**
Associate Professor, Department of CSE, Global Academy of Technology, Bengaluru -560098, venugeeta@[Link]
** Former Professor of Mathematics, Gulbarga University, Kalaburagi, Karnataka, India.

Abstract— As the study of graphs came around there was even study of domination in graphs was developed with Claude Berge in 1958,
in which he introduced the “Coefficient of external stability”, which is known as domination number of a graph. Oystein Ore
introduced the terms “Dominating Set” and “Domination Number” which was published in 1962. Since then lot of paper were
published, and has been studied extensively. The paper focus on different types of edge dominating set which are being studies along
with dominating set where only vertex is worked on or considered.
Keywords—Dominating set, Domatic number.

is a minimal dominating set of G

I. INTRODUCTION
This paper identifies the concept of edge containing . In the figure 1 showing Graph G and
domination in the field of graph theory was studied the minimal dominating set are
by many eminent researchers and still the work is .
continuing on the domination like Claude Berge in 1
the early 1960’s introduced Perfect graph. Vizing’s
Conjecture, Lovasz and Mihok, Mitchell and 3 2
Hedetniemi. Prof V R Kulli, Prof Jayaram and Prof
Sigarkanti have worked and independently G
established on lower and upper bounds for . 4 5
Domatic number was introduced by Cockayne and
Hedetniemi.
{2,3}
II. STUDY OF DEFINITIONS
3
A. Graphs
Graphs have valued functions in the field of 2
{2,4} D(G)
domination theory. This paper includes definitions {3,5} 5
and few fundamental results in the form of theorems 4
and propositions. Prof. V R Kulli, Niranjan and
Janakiram introduced a new class of intersection {1,4,5}
graphs in the field domination theory [1]. 1
A graph G = (V,E) consists of a set V of vertices
and set E of edges. Consider a simple graph as
which contain no loops and no repeated edges i.e., E Figure 1: Graph and its
is a set of unordered pairs {u,v} is distinct elements Dominating Graph
from V. The order of G is |v(G)| = n, and the size
of G is |E(G)| = m. If e = { vi, vj } E(G)}, then vi Theorem 1 The D graph D(G) of a graph G is a
and vj are adjacent. Vertex vi and e are said to be
complete bipartite graph if and only if
incident.
Observation For any is a bipartite.
B. Dominating Graph Suppose is a complete bipartite graph and
The dominating graph of a graph then there exists a component is not
is a graph with , where
trivial. For some vertex , there exists 2
S is the set all minimal dominating sets of G and
with two vertices adjacent if

1
minimal dominating sets ` such that
, a contradiction. Hence
1 2 3 4
C. Domatic Number
Definition Let be a graph and be a
partition of its vertex set is a domatic partition
of G if each class of is a dominating set in G. If 1 3
there are a maximum number of classes of domatic
partition of G then it is called domatic number of G
and is denoted by d(G) [17].

Theorem 2 For any graph F, . 2

4
Proof A graph G is domatically full if
. If T is a tree with vertices,
then it is domatically full. If is a cycle of length Figure 2: Graph G and
p and p is divisible by 3 then p is domatically full. common minimal dominating
set
Prof V R Kulli and Prof B Janakiram characterized
D. Minimal Dominating Graphs
As specified that V R Kulli and Janakiram the graphs G for which .
introduced intersection graphs in domination theory. Theorem 4 For any graph G, .
The minimal dominating graphs of a graph G is the Furthermore, if and only if every
intersection graph defined on the family of all minimal dominating set of G is independent.
minimal dominating sets of vertices in G, as shown
in figure 2. Proof If , then extend to
maximal independent set S of vertices in G. since S
Theorem 3 For any graph G with at least two is also a minimal dominating set of G, obtain
vertices, is connected if and if . Suppose , it implies in the
. same minimal dominating set S are not adjacent in
G. Thus S is independent.
Proof Let let be two
disjoint minimal dominating set of graph. Conversely, suppose every minimal dominating
Considering the case set of G is independent. Then two vertices adjacent
Case 1 : Suppose there exist 2 vertices in G cannot be adjacent in . Thus
such since is also a and since , i.e.
minimal dominating set; implies that are minimal dominating sets are connected.
connect to through .
F. Total Minimal Dominating Graph
E. Common Minimal Dominating Graphs Total minimal dominating graph of a graph
The common minimal dominating a graph G G is defined to be the interaction graph of all total
is the graph having the same vertex set as G with 2 minimal dominating set of vertices in G. This
vertices adjacent in if and only if there concept was introduced by V R Kulli and Iyer [2].
exists a minimal dominating set in G contains them.
Proposition 1 If G is a cycle of order and
then is a complete graph.

Proposition 2 If G is a - regular graph, then

.

Proposition 3 If G is a - regular graph, then

2
 and have a vertex in common. The
4
domination number of a graph G is the
minimum cardinality an edge dominating set of G.
1
It is clear from the definition that if G has at least
one edge, , if then the
2 graph G has no edges.
3
4
I. Edge Domatic Number
{3,4} Edge domatic partition of G is a partition of ,
{2,4}
all of whose classes are edge dominating set in G,
{1} hence edge domatic number of graph is denoted by
has maximum number of classes an edge
2 3 partition of G.
Connected edge domatic partition of G is a partition
Figure 3 : Graph G and Vertex Minimal
of , all of whose classes are connected edge
Dominating Graph
dominating sets in G. is a connected edge
domatic number of G which has maximum number
G. Vertex Minimal Dominating Graph of classes of a connected edge partition.
The vertex minimal dominating graph of a Theorem 6 If is a path with vertices, then
graph as shown in figure 3, is a graph
with , where S is the
collection of all minimal dominating set of G with 2 J. Connected Edge Dominating Set
vertices are adjacent if either they are An edge dominating set F of a graph G is a
adjacent in is a minimal dominating set connected edge dominating set if the induced
of G containing This concept was also introduced subgraph <F> is connected. The connected edge
by V R Kulli, Janakiram and Niranjan. domination number of G is the minimum
cardinality of a connected edge dominating set.
Theorem 5 For any graph G, connected. Theorem 7 An edge dominating set F is minimal if
Proof Since for each vertex , there exists a and only if for each edge , one of the
minimal dominating set containing , every vertex following conditions are
in is not an isolated vertex. Suppose 1)
is disconnected and are 2
components of Then there exists 2 non 2) There exists an edge such that
vertices such that .
This implies that there is minimal dominating set in
G containing a contradiction. This shows
that is connected. If observed that if Theorem 8 If F is an independent edge dominating
is complete, the G is complete and has set, then F is both a minimal edge dominating set
exactly one minimal dominating set, implies that and a minimal independent set. Conversely if F is a
maximal independent set, then F is an independent
Observation Vertex minimal dominating set edge dominating set of G[8,9].
of G is complete if and only if G is .
K. Total Domatic Number
Total domatic number was introduced by Cockayne,
H. Edge Dominating Set Hedetniemi and Dawes, it is a partition of a
Definition A set F of edges in a graph is vertex set of G is total domatic partition of G if
called an edge dominating set of G if every edge in each class of is a total dominating set of G. A
is adjacent to at least one edge in F. It can graph is a total domatic number if maximum
also be defined as a set F of edges G is called an number of classes is there in total domatic partition
edge dominating set of G if for every edge of G i.e. dt(G) [16].
, there exists an edge such that

3
Total domatic number can be found only for graphs Therefore F is an edge dominating set of G. Let
without isolated vertices, otherwise the graph has no . Then there exists such that e and f
total dominating set hence no total domatic are adjacent and is an edge
partition. dominating set of G. Thus F is a secure edge
dominating set of G.
Theorem 9 For any graph G without isolated
vertices Proposition 3. If , p is a star with vertices,
Proof For every graph G without isolated vertices, then
each total dominating set is a dominating set, thus Proof: Let E be the edge set of , where
each total domatic partition is a domatic partition.
Let Then
Hence
F is a secure total edge dominating set of . Then
. Suppose without
L. Total Dominating Set
A set F of edges in a graph is called a loss of generality, Then is not a
total dominating set of G if for every edge in E is secure total edge dominating set, so that
adjacent at least one edge if F. The total edge . Without loss of generality
domination number a graph G is the Then is not a secure total edge
minimum cardinality of a total edge dominating set dominating set, so that . Thus the
of G [1,11]. result follows the double star is the graph
M. Total Edge Domatic Number obtained from joining centers of two stars and
It was introduced by V R Kulli and Patwari and with an edge.
even worked by Zelinka, of G is the
maximum number of sets in a partition of edge set Proposition 4. If is a double star with
of G into total edge dominating sets [11,15]. vertices, then
Proof: Let E be the edge set of where
Theorem 10 For any graph G, . Let
then F is a secure total edge
N. Total Edge Dominating Set dominating set of hen .
A total edge dominating set of the edge set of Suppose Without loss of
is said to be a secure total edge generality, Clearly is not a secure
dominating set of if for every , there total edge dominating set, so that
exists an edge such that are Thus the result follows.
adjacent and is a total edge
dominating set of [10]. O. Inverse Edge Domination Number
The secure total edge domination number It was first introduced by V R Kulli and Soner it
of G is the minimum cardinality of a secure total was called as complementary edge domination
edge dominating set of G. number, to be the minimum number of edges in an
inverse edge dominating set of G.
Proposition 1. Let G be a graph without isolated Let F be a minimum edge set of G. If
vertices and isolated edges. Then contains and edge dominating set of G; then is
and this bound is sharp. called an inverse edge dominating set of G with
Proof: Clearly every secure total edge dominating respect to F which is denoted by [13].
set is a total edge dominating set. The graph Let be a minimum edge dominating set of . If
achieves this bound. contains an edge dominating set , then is
called an Inverse Edge Dominating Set of G with
Proposition 2. If F is a secure total edge respect to . The inverse edge domination number
dominating set of a graph G, then F is a secure edge
dominating set of G. of is the minimum cardinality of an
Proof: Suppose F is a secure total edge dominating inverse edge dominating set of [13].
set of . Then F is a total edge dominating set of G.

4
Theorem 11 Let be a minimum edge dominating Proposition 12. For any star
set of G if for each edge the induced
subgraph is a star then .
Proof Let F be a minimum edge dominating set of Theorem 3.13 If , is a double star with
G then under the hypothesis vertices, then ( ) = 4.
is a minimum
Proof:Let
inverse edge dominating set. Thus By
.
Proposition5, is
List of inverse edge domination number of some
a . Then is an
standard graphs are
inverse secure total edge dominating set
•
of Then . Suppose
• Without loss of generality,
Clearly is not an inverse
• secure total edge dominating set, so that
. Hence the result follows.
•
P. Secure Edge Dominating Set
• Definition A Secure Edge Dominating Set of is
an edge dominating set with the property
In all the above cases, , upper that for each there exists
bound on was given by V R Kulli and adjacent to such that is an
Soner. edge dominating set. The secure edge domination
number of is the minimum cardinality of a
Definition The Upper Inverse Secure Total Edge secure edge dominating set of G [15].
Domination Number of G is the
maximum cardinality of an inverse secure total edge Q. Secure Total Edge Dominating set
dominating set of G.A set is a minimum Definition Let be a minimum Secure Total Edge
inverse secure total edge dominating set of G. Dominating set of G. If contains a secure
Example. For the graph total edge dominating set of , then is called an
inverse secure total edge dominating set with
respect to . The inverse secure total edge
Theorem 12 Let F be a -set of a connected
domination number of G is the minimum
graph G. If a -set exists, then G has atleast 4 cardinality of an inverse secure total edge
edges. dominating set of G [14].
Proof: Let F be a -set of a connected graph G.
R. Secure and inverse secure fuzzy domination
Then . If a -set exists, A fuzzy graph is a non-empty V
then contains a secure total edge dominating together with a pair of functions
set with respect to F. Hence . Thus G such that
has at least 4 edges. for all We say that
Theorem. If , is a star with vertices, then u dominates v in G if (u, v) =
.
Proof: Let F be a -set of . By Proposition Definition. Let G be a fuzzy graph. let .A
subset D of V is called a Fuzzy Dominating Set if
3, . Let Then is a
for every there exists a vertex such
-set of for Thus that u dominates v. The minimum cardinality of a
fuzzy dominating set of G is called the fuzzy

5
domination number of G and is denoted by Conclusion
[12,13] To conclude the paper it discusses various types of
edge domination in theory of domination according
S. Secure Fuzzy Dominating Set to graph theory; few information about the
Definition. Let G be a fuzzy graph. A Secure evolution and the researchers of the concept. Topics
Fuzzy Dominating Set of a fuzzy graph G is a in the paper shows about defining, propositions,
fuzzy dominating set with the property that theorems, observations related to domination, edge
for each there exists adjacent to u domination, total edge domination, inverse edge
such that is a fuzzy dominating set. domination, minimal domination with its
The secure fuzzy domination number of G is domination graph, domination number and
the minimum cardinality of a secure fuzzy dominating set.
dominating set of G.
Definition. Let G be a fuzzy graph on . Let References
[1] V R Kulli, D K Patwari, “On the total edge domination number of a
be a minimum secure fuzzy edge dominating set graph”, In A.M. Mathai, editor, proc. Of the Symp. On Graph Theory
and Combinatorics, Kochi, Center Math. Sci. Trivandrum, series:
of a fuzzy graph G. If contains a secure fuzzy Publication21 (1991) 75-81.
edge dominating set then is called an [2] V R Kulli, B Janakiram, ”The minimal dominating graph”, Graph
Theory notes of NewYork, New York Academy of Sciences, XXVIII,
inverse secure fuzzy edge dominating set with 1995,12-15.
respect to F. The secure fuzzy edge domination [3] V R Kulli, R RIyer, “The total minimal dominating graph of a graph”,
manuscript.
number of G is the minimum cardinality
[4] Schiermeyer, I.: Efficiency in exponential time for domination-type
of an inverse secure fuzzy edge dominating set in G. problems. Discrete Appl. Math.156, 3291–3297 (2008)
[5] Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through
T. Inverse Secure Fuzzy Dominating Set enumerating maximal independentsets and other techniques. Theory
Definition. Let G be a fuzzy graph. Let D be a Comput. Syst. 42, 563–587 (2007)
[6] Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two
minimum secure fuzzy dominating set of a fuzzy techniques of combining branchingand treewidth. Algorithmica 54, 181–
graph G. If contains a secure fuzzy 207 (2009)
[7] Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23–28
dominating set then s called an inverse (1965)
secure fuzzy dominating set with respect to D. The [8] M.A. Rajan, M. Girish Chandra, Lokanatha C. Reddy, Prakash
Hiremath, Concepts of graph theory relevant to ad-hoc networks,
inverse secure fuzzy domination number International Journal of Computers, Communications and Control
of G is the minimum cardinality of an inverse (2008) 465–469.
[9] Venugeetha Y, Dr. B . P. Mallikarjunaswamy, Prof. V R Kulli, “Theory
secure fuzzy dominating set in G[9]. of Edge Domination in Graphs-A Study”, IOSR Journal of Engineering
(IOSRJEN) [Link] ISSN (e): 2250-3021, ISSN (p): 2278-
U. Fuzzy Edge Domination Number 8719Vol. 08, Issue7 (July. 2018), ||V (IV) || 84-92.
An edge of a fuzzy graph is called an [10] K. M. Alzoubi, “Connected dominating set and its induced position-less
sparse spanner for mobile ad hoc networks”. In Proceedings of the
effective edge if Eighth IEEE Symposium on Computers and Communications, June
Definition. Let G be a fuzzy graph on A 2003.
subset F of E is called a fuzzy edge dominating set [11] Venugeetha Y, Ashwini C, Dr. B . P. Mallikarjunaswamy “A Study On
Wireless Sensor Networks” Nov 2015 Volume 2, Issue 11, 454-459
if for every edge in is adjacent to at least one [12] [Link], [Link], “Domination in fuzzy graph”,
effective edge in F. The minimum cardinality of a [Link], “Inverse total edge domination in graphs.” In Advances in
Domination Theory I, [Link] ed., Vishwa International Publications,
fuzzy edge dominating set of G is called the Fuzzy Gulbarga, India (2012) 35-44Advances inFuzzy sets and Systems, 1(1)
(2006) 17-26.
Edge Domination Number of G and it is denoted
[13] [Link], [Link], “Domination in fuzzy graphs”,
by [9]. Pattern Recognit. Lett.19(9) (1998) 878-791.
[13]. [Link], “Secure edge domination in graphs”, Annals of Pure and
V. Secure Fuzzy Edge Dominating Set Applied Mathematics, 12(1) (2016) 95-99.
Definition. Let G be a fuzzy graph on A [14]. [Link], “Inverse total edge domination in graphs.” In Advances in
Domination Theory I, [Link] ed., Vishwa International Publications,
Secure Fuzzy Edge Dominating Set of a fuzzy Gulbarga, India (2012) 35-44.
graph G is a fuzzy edge dominating set with [15]. [Link], “Secure and Inverse Secure Total Edge Domination and
Some Secure and Inverse Secure Fuzzy Domination Parameters”, Intern.
the property that for each edge , there J. Fuzzy Mathematical Archive Vol. 11, No.1, 2016, 25-30 ISSN: 2320
exists adjacent to e such that –3242 (P), 2320 –3250 (online) Published on 19 September 2016,
[Link]
is a fuzzy edge dominating set. The [16]. E J Cockayne, R M Dawes, S T Hedetniemi, “Total domination in
secure fuzzy edge domination number of G graphs”, Networks, 10 1980, 211-219.
[17]. E J Cockayne, S T Hedetniemi, “Towards a theory of domination in
is the minimum cardinality of a secure fuzzy edge graphs”, Networks, 7 1977, 247-261.
dominating set of G.

6
 7

View publication stats