Published January 1, 2023
| Version v1
Journal article
Open
On total domination and minimum maximal matchings in graphs
Description
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 mu*(G) and gamma(t)(G) be the minimum cardinalities of a maximal matching and a total dominating set in G, respectively. Let delta(G) denote the minimum degree in graph G. We observe that gamma(t)(G) <= 2 mu*(G) when 1 <= delta(G) <= 2 and gamma(t)(G) <= 2 mu*(G) - delta(G) + 2 when delta(G) >= 3. We show that the upper bound for the total domination number is tight for every fixed delta(G). We provide a constructive characterization of graphs G satisfying gamma(t)(G) = 2 mu*(G) and a polynomial time procedure to determine whether gamma(t)(G) = 2 mu*(G) for a graph G with minimum degree two.
Files
bib-d936b8c3-e9f1-487f-a211-9df592e7f54b.txt
Files
(124 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:1ee711d38ca28c1bb2856c0e73594183
|
124 Bytes | Preview Download |