|
|||||
|
|
On matching and total domination in graphs |
|
| Authors: | Michael A Henning Liying Kang Erfang Shan Anders Yeo |
| Institution: | a School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg 3209, South Africa b Department of Mathematics, Shanghai University, Shanghai 200444, China c Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 OEX, UK |
| Abstract: | A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. 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 k-regular graph with k?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. |
| Keywords: | 05C69 |
| 本文献已被 ScienceDirect 等数据库收录！ | |