کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650544 | 1342492 | 2008 | 7 صفحه PDF | دانلود رایگان |

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G , denoted by γt(G)γt(G). A graph is claw-free if it does not contain K1,3K1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21–45] that if G is a connected graph of order n with minimum degree at least two and G∉{C3,C5G∉{C3,C5, C6C6, C10}C10}, then γt(G)⩽4n/7γt(G)⩽4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γt(G)⩽(n+2)/2γt(G)⩽(n+2)/2 and we characterize those graphs for which γt(G)=⌊(n+2)/2⌋γt(G)=⌊(n+2)/2⌋.
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3213–3219