7
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Chris: I think the second question asks for a description of all induced subgraphs of Cayley graphs. The question is equivalent to this one. Let $G$ be a finite (directed) graph. Assign different generator for each positive edge of $G$. For every loop from the generating set of the fundamental group of $G$ (choose a base point) assign the relator - the product of edge labels of that loop. You get a group presentation. Question: for which $G$ the group admits a finite quotient such that the natural image from $G$ to the Cayley graph of $G$ is an induced subgraph. It may be undecidable. $\endgroup$
    – user6976
    Commented Jan 4, 2012 at 20:30
  • $\begingroup$ @Mark: I think you are right. I suspect even recognizing which graphs arise as subgraphs induced by the neighbors of a vertex in a Cayley might be undecidable. $\endgroup$
    – Chris Godsil
    Commented Jan 4, 2012 at 22:07
  • $\begingroup$ Mark, I proved it is undecidable if a finite labeled graph embeds in the Cayley graph of a finite group. It follows as you hint at from the undecidability of the uniform word problem for finite groups. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 5, 2012 at 1:40
  • $\begingroup$ @Ben: Yes, embeddability is undecidable, but embeddability as an induced subgraph may be different. $\endgroup$
    – user6976
    Commented Jan 5, 2012 at 3:22
  • $\begingroup$ Thanks a lot for your very useful answers, specially thanks dear Godsil. $\endgroup$
    – Shahrooz
    Commented Jan 5, 2012 at 10:18
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear McKay, based on this paper "Neighbourhood Graphs of Cayley Graphs for Finitely-generated Groups", I am constructing some examples that you pointed it in your answer. $\endgroup$
    – Shahrooz
    Commented Jan 5, 2012 at 10:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Actually, the paper shows being a subgraph of a Cayley graph is undecidable. But the induced subgraph problem should be equivalent. One can just create from a given finite directed labeled graph a finite set of labeled graphs including all possible ways edges with those labels between the existing vertices might be added (including not adding any) and the original graph should embed iff one of these "completions" is an induced subgraph of a Cayley graph. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 5, 2012 at 2:11
  • $\begingroup$ Note that you are dealing with labeled graphs while the OP is talking about non-labeled graphs. (As for induced subgraphs, it may not be such a big difference. ) $\endgroup$
    – user6976
    Commented Jan 5, 2012 at 4:20
  • $\begingroup$ You are right, undecidability for labeled doesnt imply the unlabeled case. Induced doesn't make a difference. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 5, 2012 at 8:29
2
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Mohsen, Thanks for your referencing. $\endgroup$
    – Shahrooz
    Commented Oct 19, 2012 at 10:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .