کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650544 1342492 2008 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Total domination in claw-free graphs with minimum degree 2
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Total domination in claw-free graphs with minimum degree 2
چکیده انگلیسی

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⌋.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3213–3219
نویسندگان
, ,