16
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You don't need differential topology, just ordinary alg. top. will do. There is a useful connection to combinatorial group theory here and browsing through that area may give you ideas w.r.t say Cayley graphs, that will help. One problem that you face is what `the same' should mean in your setting. One idea might be to look at the valence of nodes, but that may be what you have already looked at. I am not a graph theorist so may not be understanding some of the terminology that you are using. $\endgroup$
    – Tim Porter
    Commented Feb 9, 2010 at 9:03
  • $\begingroup$ As Tim says, this ought to be connected to a much-studied POV in geometric/combinatorial group theory: I don't know where this "started", but perhaps these notes by Brent Everitt arxiv.org/abs/math.GR/0606326 might have useful pointers, if not answers for your questions. $\endgroup$
    – Yemon Choi
    Commented Feb 9, 2010 at 9:23
  • 1
    $\begingroup$ I don't think there's anything directly relevant to this question, but you might find Jeff Erickson's notes on computational topology interesting anyway: compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/schedule.html $\endgroup$
    – Eric Peterson
    Commented Feb 9, 2010 at 14:33

4 Answers 4

Reset to default
32
$\begingroup$

Two finite graphs have the same universal cover iff they have a common finite cover. This surprising fact was first proved by Tom Leighton here:

Frank Thomson Leighton, Finite common coverings of graphs. 231-238 1982 33 J. Comb. Theory, Ser. B

I'm quite sure the paper also presents an algorithm for determining if this is the case for two given graphs; essentially you develop a refined "degree" sequence for the graphs, starting from "# of vertices of degree k" and refining to "# of vertices of degree k with so-and-so neighbors of degree l" etc.

As an aside, the reason this result is so surprising is that it says something highly non-trivial about groups acting on trees (any two subgroups of Aut(T) with a finite quotient are commensurable, up to conjugation), and proving this result directly via group-theoretic methods is surprisingly difficult (and interesting). There's a paper of Bass and Kulkarni which pretty much does just that.

Edit: I just ran a quick search and found this sweet overview: "On Leighton's Graph Covering Theorem".

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Definitely a seminal paper in the topological theory of graphs! $\endgroup$
    – Pete L. Clark
    Commented Mar 8, 2010 at 21:03
10
$\begingroup$

An addendum on the question of polynomial time. In a 1991 paper, which can be found here, Abello, Fellows, and Stillwell proved that there is a fixed graph H for which the problem of deciding whether a given G covers H is NP-complete.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$
    – Sam Nead
    Commented Feb 9, 2010 at 15:11
  • 2
    $\begingroup$ @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. $\endgroup$
    – John Stillwell
    Commented Feb 10, 2010 at 0:15
4
$\begingroup$

If two graphs have a common cover, then they have a common universal cover. The "maximal" cover is therefore unique. In general, the reverse is not true. The "minimal" common cover may not be unique. This was shown by Wilfried Imrich and me. See also European Journal of Combinatorics Volume 29, Issue 5, July 2008, Pages 1116-1122

Improve this answer
$\endgroup$
4
$\begingroup$

Maybe this is of interest to you. In section 3.3 of the below paper (see also 2.2), the universal covers are extended from graphs to degree matrices, and some conditions are given under which two degree matrices (graphs) have the same universal cover: Locally constrained graph homomorphisms and equitable partitions J.Fiala, D.Paulusma and J.A.Telle European Journal of Combinatorics. Volume 29.(4) p. 850-880

Improve this answer
$\endgroup$

You must log in to answer this question.

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