Cayley graphs and its subgraphs I have two questions about Cayley graphs. Any answers will be appreciate.
1) Do we have any Cayley graph that has Petersen graph as its induced subgraph?
2) Suppose $Cay(G,S)$ be a Cayley graph that $G$ is a finite group. Can we characterize any induced subgraphs of $Cay(G,S)$?
Thanks for any answer and guidance. 
 A: Every graph is an induced subgraph of some vertex transitive graph (a result I first learned from Chris).  In fact Fink and Ruiz showed in 1984 that for any graph $H$, there is a circulant graph $G~$ whose edge set can be partitioned into copies of $H~$ that are induced subgraphs of $G$. The second question is more difficult, but is there a reason (such as an example) to believe that some graphs cannot be the neighbourhood graphs of Cayley graphs?  The neighbourhood graphs of circulant graphs always have an automorphism of order 2, so cyclic groups are not sufficient in this case. 
A: In my paper
The uniform word problem for groups and finite Rees quotients of E-unitary inverse semigroups, Journal of Algebra, Volume 266, Number 1, 1 August 2003 , pp. 1-13(13)
I prove that it is undecidable whether a finite directed labeled graph has a label preserving-embedding into the Cayley graph of a finite group.  More generally, if V is a class of groups closed under finite direct products, subgroups and homomorphic images, then the embeddability of a finite labeled graph into the Cayley graph of a group in V is equivalent to the uniform word problem for V.
If the graph is unlabeled one can try all the finitely many labelings over an alphabet of size the number of edges in the graph. So the second problem is undecidable. 
A: To answer your first question, take a look at [P. Erdos and A. B. Evans. Representations of graphs and orthogonal Latin square graphs. J. Graph Theory 13 (1989), no. 5, 593-595.]
Actually, It was shown that every graph $G$ is the induced subgraph of a circulant graph (a cayley graph on a cyclic group).
A: If $X$ is a vertex-transitive graph and the stabilizer of a vertex has order $m$, then the lexicographic product of $K_m$ by $X$ is a Cayley graph. We get the lexicographic product here by replacing each vertex of $X$ by $K_m$ and, where two vertices of $X$ are adjacent, join
each vertex in one $K_m$ to each vertex in the other. So this product contains copies of $X$ as
an induced subgraph and is a Cayley graph for $Aut(X)$. The result and the construction are due to Sabidussi.
You second question is too vague to admit an answer. 
