Timeline for Checking if two graphs have the same universal cover
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2010 at 0:15 | comment | added | John Stillwell | @Sam: I take your point; there is no obvious equivalence between deciding whether a common cover exists, and deciding whether one graph covers another. I should have looked at Leighton's proof, which shows that graphs have a common cover if and only if they have the same "degree refinement", a matrix which is pretty clearly computable in polynomial time. This surprises me, because I did not expect testing for common covering to be easier than testing for covering. | |
| Feb 9, 2010 at 15:11 | comment | added | Sam Nead | Detecting if given G covers fixed H sounds harder than deciding if given G, H have a common finite cover. Is there some non-obvious equivalence? I feel like I am missing something here... | |
| Feb 9, 2010 at 10:43 | history | answered | John Stillwell | CC BY-SA 2.5 |