Stable Kneser Graphs are almost all not weakly Hom-Idempotent

Pablo Torres (1, 2) , Mario Valencia-Pabon (3, 4)

1 Universidad Nacional de Rosario [Santa Fe]
2 CONICET - Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
3 ORPAILLEUR - Knowledge representation, reasonning
4 LIPN - Laboratoire d'Informatique de Paris-Nord

A graph G is said to be hom-idempotent if there is an homomorphism from G 2 to G, and weakly hom-idempotent if for some n ≥ 1 there is a homomorphism from G n+1 to G n . Larose et al. [Eur. J. Comb. 19:867-881, 1998] proved that Kneser graphs KG(n, k) are not weakly hom-idempotent for n ≥ 2k + 1, k ≥ 2. We show that 2-stable Kneser graphs KG(n, k) 2−stab 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.

Mots clés: Cartesian product of graphs; Stable Kneser graphs; Cayley graphs; Hom-idempotent graphs

Domaines: Mathématiques [math]

Pablo Torres, Mario Valencia-Pabon. Stable Kneser Graphs are almost all not weakly Hom-Idempotent . 2015. ⟨hal-01119741⟩