It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere.
You can define a notion of "covering graph" in graph theory, analogous to covering spaces. (Actually I think there's some sense -- maybe in differential topology -- in which the notions agree exactly, but that's not the question.) Anyway, it behaves like a covering space -- it lifts paths and so on.
There's also a "universal cover," which I think satisfies the same universal property as topological universal covers but I'm not sure. Universal covers are acyclic (simply connected) in graph theory, so they're trees, usually infinite. The universal cover doesn't determine the graph; for instance, any two k-regular graphs (k > 1) have the same universal cover. You can construct plenty of other pairs, too.
I'm interested in necessary and sufficient conditions for two graphs $G, H$ to have the same universal cover. One such condition (I'm pretty sure!) is whether you can give a 1-1 correspondence between trails in $G$ and trails in $H$ that preserves degree sequences. Unfortunately this doesn't help me much, since this is still basically an infinite condition. Is there some less-obvious but more easily checkable condition? In particular is it possible to determine if two (finite) graphs have the same universal cover in polynomial time?
No comments:
Post a Comment