کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648747 1342427 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounds on total domination in claw-free cubic graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bounds on total domination in claw-free cubic graphs
چکیده انگلیسی

A set SS of vertices in a graph GG is a total dominating set, denoted by TDS, of GG if every vertex of GG is adjacent to some vertex in SS (other than itself). The minimum cardinality of a TDS of GG is the total domination number of GG, denoted by γt(G)γt(G). If GG does not contain K1,3K1,3 as an induced subgraph, then GG is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207–210.] that if GG is a graph of order nn with minimum degree at least three, then γt(G)⩽n/2γt(G)⩽n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9–19.] which shows that this bound of n/2n/2 is sharp. However, every graph in these two families, except for K4K4 and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2n/2 can be improved if we restrict GG to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if GG is a connected claw-free cubic graph of order n⩾10n⩾10, then γt(G)⩽5n/11γt(G)⩽5n/11.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 16, 28 August 2008, Pages 3491–3507
نویسندگان
, ,