Timeline for Cayley graphs and its subgraphs
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2012 at 1:41 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 17 characters in body
|
| Jan 5, 2012 at 8:29 | comment | added | Benjamin Steinberg | You are right, undecidability for labeled doesnt imply the unlabeled case. Induced doesn't make a difference. | |
| Jan 5, 2012 at 4:20 | comment | added | user6976 | 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. ) | |
| Jan 5, 2012 at 2:11 | comment | added | Benjamin Steinberg | 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. | |
| Jan 5, 2012 at 2:05 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
added 7 characters in body
|
| Jan 5, 2012 at 1:47 | history | answered | Benjamin Steinberg | CC BY-SA 3.0 |