کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648898 1342435 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lower bounds for the domination number and the total domination number of direct product graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Lower bounds for the domination number and the total domination number of direct product graphs
چکیده انگلیسی

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: γ(×i=1tKni)≥t+1,t≥3. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γt(G×H)=γ(G)+γ(H)−1γt(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 23, 6 December 2010, Pages 3310–3317
نویسندگان
,