کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650527 | 1342490 | 2008 | 6 صفحه PDF | دانلود رایگان |
A set MM of edges of a graph GG is a matching if no two edges in MM are incident to the same vertex. A set SS of vertices in GG is a total dominating set of GG if every vertex of GG is adjacent to some vertex in SS. The matching number is the maximum cardinality of a matching of GG, while the total domination number of GG is the minimum cardinality of a total dominating set of GG. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every kk-regular graph with k⩾3k⩾3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.
Journal: Discrete Mathematics - Volume 308, Issue 11, 6 June 2008, Pages 2313–2318