Timeline for Cayley graphs and its subgraphs
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2012 at 19:27 | vote | accept | Shahrooz | ||
| Jan 5, 2012 at 10:18 | comment | added | Shahrooz | Thanks a lot for your very useful answers, specially thanks dear Godsil. | |
| Jan 5, 2012 at 3:22 | comment | added | user6976 | @Ben: Yes, embeddability is undecidable, but embeddability as an induced subgraph may be different. | |
| Jan 5, 2012 at 1:40 | comment | added | Benjamin Steinberg | 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. | |
| Jan 4, 2012 at 22:07 | comment | added | Chris Godsil | @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. | |
| Jan 4, 2012 at 22:04 | history | edited | Chris Godsil | CC BY-SA 3.0 |
fixed spelling
|
| Jan 4, 2012 at 20:30 | comment | added | user6976 | @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. | |
| Jan 4, 2012 at 19:10 | history | answered | Chris Godsil | CC BY-SA 3.0 |