Leighton's theorem

from Wikipedia, the free encyclopedia

The set of Leighton is a theorem from the mathematical field of graph theory .

Overlay of graphs: C is a 2-fold overlay of H.
Overlay of graphs: T is an infinite overlay of H.

It was proved by Dana Angluin and A. Gardiner for regular graphs and by Frank Thomson Leighton in the general case. Hyman Bass and Ravi Kulkarni gave evidence under the Bass-Serre theory .

Leighton's theorem

If two finite graphs have a common overlay , then they have a common finite overlay .

literature

  • Dana Angluin, A. Gardiner: Finite common coverings of pairs of regular graphs, J. Combin. Theory Ser. 1981 B 30: 184-187.
  • Frank Thomson Leighton: Finite Common Coverings of Graphs, J. Comb. Theory, Series B, 33: 231-138 (1982).
  • Hyman Bass, Ravi Kulkarni: Uniform tree lattices, J. Amer. Math. Soc. 3: 843-902 (1990).
  • Hyman Bass: Covering theory for graphs of groups, J. Pure Appl. Algebra, 89: 3-47 (1993).
  • Seonhee Lim, Anne Thomas: Covering theory for complexes of groups, J. Pure Appl. Alg. 212 (2008), 1632-1663.

Web links