کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421055 684022 2006 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on acyclic domination number in graphs of diameter two
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A note on acyclic domination number in graphs of diameter two
چکیده انگلیسی

A subset SS of the vertex set of a graph GG is called acyclic   if the subgraph it induces in GG contains no cycles. SS is called an acyclic dominating   set of GG if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γa(G)γa(G), is called the acyclic domination number   of GG. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151–165] introduced the concept of acyclic domination and posed the following open problem: if δ(G)δ(G) is the minimum degree of GG, is γa(G)⩽δ(G)γa(G)⩽δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive kk, there is a graph GG with diameter two such that γa(G)-δ(G)⩾kγa(G)-δ(G)⩾k.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 1019–1022
نویسندگان
, , ,