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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Oct 22, 2013 at 12:16
-
$\begingroup$ I'm sure this proof works, but it needs a bit more. A complete graph (which is a Kneser graph) on a non-prime number of vertices is a strong product but your argument would exclude it. The Kneser graph $K_{n;n/2}$ is also a strong product I think. $\endgroup$ Oct 22, 2013 at 14:00
-
$\begingroup$ Could you link the paper as well? So it all boils down to finding if the automorphism group is a direct or a wreath product? Could arguments such ones here also answer the following question? Given vertex transitive $G$ and $H$ such that $|\mathcal{V}(G)|<|\mathcal{V}(H)|$ and $\mathcal{Aut}(G)\supset\mathcal{Aut}(H)$, is it true $G\leq H$? Conversely if $G\leq H$, what can we say about $\mathcal{Aut}(G)$ and $\mathcal{Aut}(H)$? $\endgroup$– TurboOct 22, 2013 at 20:50
-
$\begingroup$ The Doerfler-Imrich paper is 1969, and in German. The Feigenbaum-Schaeffer paper comes up on google. There is nothing useful to be said about the relation between the automorphism group of a graph and a subgraph. $\endgroup$ Oct 22, 2013 at 21:22