On total domination and minimum maximal matchings in graphs

Abstract: A subset

M

of the edges of a graph

G

is a matching if no two edges in

M

are incident. A maximal matching is a matching that is not contained in a larger matching. A subset

S

of vertices of a graph

G

with no isolated vertices is a total dominating set of

G

if every vertex of

G

is adjacent to at least one vertex in

S

. Let

m u^{*} (G)

and

g a m m a_{t} (G)

be the minimum cardinalities of a maximal matching and a total dominating set in

G

, respectively. Let

d e l t a (G)

denote the minimum degree in graph

G

. We observe that

g a m m a_{t} (G) l e q 2 m u^{*} (G)

when

1 l e q d e l t a (G) l e q 2

and

g a m m a_{t} (G) l e q 2 m u^{*} (G) - d e l t a (G) + 2

when

d e l t a (G) g e q 3

. We show that the upper bound for the total domination number is tight for every fixed

d e l t a (G)

. We provide a constructive characterization of graphs

G

satisfying

g a m m a_{t} (G) = 2 m u^{*} (G)

and a polynomial time procedure to determine whether

g a m m a_{t} (G) = 2 m u^{*} (G)

for a graph

G

with minimum degree two.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: On total domination and minimum maximal matchings in graphs