کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419030 | 681732 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Global offensive alliances in graphs and random graphs
ترجمه فارسی عنوان
اتحاد جهانیان تهاجمی در نمودارها و نمودارهای تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتحاد جهانیان تهاجمی، توالی درجه مرزهای بالا نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A global offensive alliance in a graph G=(V,E)G=(V,E) is a subset SS of VV such that for every vertex vv not in SS at least half of the vertices in the closed neighborhood of vv are in SS. The cardinality of a minimum size global offensive alliance in GG is called the global offensive alliance number of GG. We give an upper bound on the global (strong) offensive alliance number of a graph in terms of its degree sequence. We also study global offensive alliances of random graphs. In particular, it is proved that if p(logn)1/2→∞p(logn)1/2→∞ then with high probability G(n,p)G(n,p) has a global offensive alliance of size at most cncn if c>1/2c>1/2 and no global offensive alliance of size at most cncn if c<1/2c<1/2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 2, 19 February 2014, Pages 522–526
Journal: Discrete Applied Mathematics - Volume 164, Part 2, 19 February 2014, Pages 522–526
نویسندگان
Ararat Harutyunyan,