کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656816 | 1632985 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the ultimate categorical independence ratio
ترجمه فارسی عنوان
در رابطه با استقلال قطعی نهایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تعداد استقلال، نسبت استقلال، محصول طبقهبندی شده، محصول مستقیم، ارزش همبستگی پارامترهای گراف
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Brown, Nowakowski and Rall defined the ultimate categorical independence ratio of a graph G as A(G)=limk→∞i(G×k), where i(G)=α(G)|V(G)| denotes the independence ratio of a graph G , and G×kG×k is the kth categorical power of G . Let a(G)=max{|U||U|+|NG(U)|:U is an independent set of G}, where NG(U)NG(U) is the neighborhood of U in G . In this paper we answer a question of Alon and Lubetzky, namely we prove that A(G)=a(G)A(G)=a(G) if a(G)⩽12, and A(G)=1A(G)=1 otherwise. We also discuss some other open problems related to A(G)A(G) which are immediately settled by this result.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 29–39
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 29–39
نویسندگان
Ágnes Tóth,