|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|5777422||1632755||2017||8 صفحه PDF||سفارش دهید||دانلود کنید|
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.
Journal: European Journal of Combinatorics - Volume 62, May 2017, Pages 50-57