کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419030 681732 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Global offensive alliances in graphs and random graphs
ترجمه فارسی عنوان
اتحاد جهانیان تهاجمی در نمودارها و نمودارهای تصادفی
کلمات کلیدی
اتحاد جهانیان تهاجمی، توالی درجه مرزهای بالا نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
,