کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656816 1632985 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the ultimate categorical independence ratio
ترجمه فارسی عنوان
در رابطه با استقلال قطعی نهایی
کلمات کلیدی
تعداد استقلال، نسبت استقلال، محصول طبقهبندی شده، محصول مستقیم، ارزش همبستگی پارامترهای گراف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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