Domination in graphs
Loading...
Date
2008-05
Authors
Che Na Wi, Mohd Shahbudin
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The theory of graphs which came into existence when the Swiss mathematician Euler
settled the famous problem of"seven bridges of Konigsberg", has grown into an important
branch of Mathematics finding applications in many different fields.
A graph is a discrete structure consisting of vertices and edges that connect these
vertices. Among several notions associated with graphs, domination is an important
concept which has been investigated by researchers extensively. In a graph, a dominating
set is a subset of the set of vertices such that every vertex of the graph is either in the subset
or is adjacent to a vertex in the subset.
We first introduce the concept of a graph and review certain basic definitions and
results pertaining to the notion of a graph. We then introduce the concept of domination in
a graph and discuss its properties. As an application, we indicate a real life situation where
domination plays a role.
Then we introduce two notions of domination in a graph called independent domination
and connected domination and discuss their properties.
Finally, we also introduce concept of equal domination that relates independent
domination and connected domination. The presentation of the material is based on the
research work carried out in [ 2, 10,11 ].
Description
Keywords
Graph