کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649549 1342459 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Total domination and total domination subdivision number of a graph and its complement
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Total domination and total domination subdivision number of a graph and its complement
چکیده انگلیسی

A set S   of vertices of a graph G=(V,E)G=(V,E) with no isolated vertex is a total dominating set   if every vertex of V(G)V(G) is adjacent to some vertex in S. The total domination number  γt(G)γt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number  sdγt(G)sdγt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n⩾4n⩾4, minimum degree δδ and maximum degree ΔΔ. We prove that if each component of G   and G¯ has order at least 3 and G,G¯≠C5, then γt(G)+γt(G¯)⩽2n3+2 and if each component of G   and G¯ has order at least 2 and at least one component of G   and G¯ has order at least 3, then sdγt(G)+sdγt(G¯)⩽2n3+2. We also give a result on γt(G)+γt(G¯) stronger than a conjecture by Harary and Haynes.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 17, 6 September 2008, Pages 4018–4023
نویسندگان
, , ,