کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
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