With respect to the Strong product, is the Kneser graph prime and if not how does one find a prime decomposition? Are there any references or algorithms?



Factors of Kneser graph
Doerfler and Imrich and (independently) MacKenzie showed that any connected graph has a unique factorization into graphs prime relative to the strong product. It follows that if a connected graph is not prime, its automorphism group is the direct product of two non-identity groups, or is a wreath product. But the automorphism group of the Kneser graph $K\_{v:k}$ is the symmetric group on $v$ points, and this is neither a direct nor a wreath product.


Edit: As Brendan notes below, this argument only works for Kneser graphs that are connected and not complete.


There is a polynomial time algorithm for decomposition relative to the strong product, due to Feigenbaum and Schaeffer. It's likely that if you work through this you will find other ways to show that the Kneser graphs are prime.


