کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5777422 1632755 2017 8 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Shifts of the stable Kneser graphs and hom-idempotence
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Shifts of the stable Kneser graphs and hom-idempotence
چکیده انگلیسی

A graph G is said to be hom-idempotent if there is a homomorphism from G2 to G, and weakly hom-idempotent if for some n≥1 there is a homomorphism from Gn+1 to Gn. Larose et al. (1998) proved that Kneser graphs KG(n,k) are not weakly hom-idempotent for n≥2k+1, k≥2. For s≥2, we characterize all the shifts (i.e., automorphisms of the graph that map every vertex to one of its neighbors) of s-stable Kneser graphs KG(n,k)s−stab and we show that 2-stable Kneser graphs are not weakly hom-idempotent, for n≥2k+2, k≥2. Moreover, for s,k≥2, we prove that s-stable Kneser graphs KG(ks+1,k)s−stab are circulant graphs and so hom-idempotent graphs. Finally, for s≥3, we show that s-stable Kneser graphs KG(2s+2,2)s−stab are cores, not χ-critical, not hom-idempotent and their chromatic number is equal to s+2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 62, May 2017, Pages 50-57
نویسندگان
, ,