کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512184 | 1632456 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stratification and domination in graphs with minimum degree two
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. We investigate the F-domination number when F is a 2-stratified path P3 on three vertices rooted at a blue vertex which is an end-vertex of the P3 and is adjacent to a blue vertex with the remaining vertex colored red. We show that for a connected graph of order n with minimum degree at least two this parameter is bounded above by (n-1)/2 with the exception of five graphs (one each of orders four, five and six and two of order eight). For n⩾9, we characterize those graphs that achieve the upper bound of (n-1)/2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 301, Issues 2â3, 6 October 2005, Pages 175-194
Journal: Discrete Mathematics - Volume 301, Issues 2â3, 6 October 2005, Pages 175-194
نویسندگان
Michael A. Henning, J.E. Maritz,