On total domination and minimum maximal matchings in graphs
Quaestiones Mathematicae, cilt.46, sa.6, ss.1119-1129, 1 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 46 Sayı: 6
- Basım Tarihi: 1
- Doi Numarası: 10.2989/16073606.2022.2057879
- Dergi Adı: Quaestiones Mathematicae
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, MathSciNet, zbMATH
- Sayfa Sayıları: ss.1119-1129
- Anahtar Kelimeler: Minimum maximal matching, total domination number
- Ankara Yıldırım Beyazıt Üniversitesi Adresli: Hayır
Özet
© 2022 NISC (Pty) Ltd.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 µ*(G) and γt (G) be the minimum cardinalities of a maximal matching and a total dominating set in G, respectively. Let δ(G) denote the minimum degree in graph G. We observe that γt (G) ≤ 2µ*(G) when 1 ≤ δ(G) ≤ 2 and γt (G) ≤ 2µ*(G) − δ(G) + 2 when δ(G) ≥ 3. We show that the upper bound for the total domination number is tight for every fixed δ(G). We provide a constructive characterization of graphs G satisfying γt (G) = 2µ*(G) and a polynomial time procedure to determine whether γt (G) = 2µ*(G) for a graph G with minimum degree two.