Advances and Applications in Discrete Mathematics
Volume 5, Issue 2, Pages 159 - 169
(April 2010)
|
|
ON MINUS EDGE DOMINATION NUMBER OF GRAPHS
Huazhu Chen, Suohai Fan, Wansheng Liao and Yuyan Cui
|
be a simple graph. For an edge e
of G, the closed edge-neighborhood of e is the set
is adjacent to
A function
is called a minus edge domination
function (MEDF) of G if
for every edge e
of G. The minus edge domination number
of G is defined as
In this paper, it is proved that
for any graph G,
where
is the number of edges in a minimum
maximal matching of a graph G. These
bounds are best possible and extremal graphs are characterized for trees.