کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650297 1342483 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On equality in an upper bound for the restrained and total domination numbers of a graph
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On equality in an upper bound for the restrained and total domination numbers of a graph
چکیده انگلیسی

Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S   and to a vertex in V⧹SV⧹S. The restrained domination number of G  , denoted by γr(G)γr(G), is the minimum cardinality of an RDS of G  . A set S⊆VS⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G   without isolated vertices, denoted by γt(G)γt(G), is the minimum cardinality of a TDS of G.Let δδ and ΔΔ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n   with δ⩾2δ⩾2, then it is shown that γr(G)⩽n-Δγr(G)⩽n-Δ, and we characterize the connected graphs with δ⩾2δ⩾2 achieving this bound that have no 3-cycle as well as those connected graphs with δ⩾2δ⩾2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211–219] showed that if G   is a connected graph of order n⩾3n⩾3 and Δ⩽n-2Δ⩽n-2, then γt(G)⩽n-Δγt(G)⩽n-Δ. We further characterize the connected graphs G   of order n⩾3n⩾3 with Δ⩽n-2Δ⩽n-2 that have no 3-cycle and achieve γt(G)=n-Δγt(G)=n-Δ.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 22, 28 October 2007, Pages 2845–2852
نویسندگان
, , , , , ,