Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Total domination and matching numbers in claw-free graphs. | Total domination and matching numbers in claw-free graphs 1 Michael A. Henning and 2Anders Yeo 1 School of Mathematical Sciences University of KwaZulu-Natal Pietermaritzburg 3209 South Africa henning@ 2Department of Computer Science Royal Holloway University of London Egham Surrey TW20 OEX UK anders@ Submitted Apr 18 2006 Accepted Jun 30 2006 Published Jul 28 2006 Mathematics Subject Classification 05C69 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. The matching number of G is the maximum cardinality of a matching of G. 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 minimum cardinality of a total dominating set of G is the total domination number of G. If G does not contain K1 3 as an induced subgraph then G is said to be claw-free. 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. In this paper we use transversals in hypergraphs to characterize connected claw-free graphs with minimum degree at least three that have equal total domination and matching numbers. Keywords claw-free matching number total domination number 1 Introduction Total domination in graphs was introduced by Cockayne Dawes and Hedetniemi 3 and is now well studied in graph theory. The literature on this subject has been surveyed and detailed in the two books by Haynes Hedetniemi and Slater 5 6 . Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R59 1 Let G V E be a graph with vertex set V and edge set E. A set S Q V is a total dominating set abbreviated TDS of G if every vertex in V is adjacent to a vertex in S. Every graph without isolated vertices has a TDS since S V is such a set. The total domination number of G denoted by Yt G is the minimum
