Der Satz von Leighton ist ein Lehrsatz aus dem mathematischen Gebiet der Graphentheorie.

Überlagerung von Graphen: C ist eine 2-fache Überlagerung von H.
Überlagerung von Graphen: T ist eine unendliche Überlagerung von H.

Er wurde von Dana Angluin und A. Gardiner für reguläre Graphen und von Frank Thomson Leighton im allgemeinen Fall bewiesen. Hyman Bass und Ravi Kulkarni gaben einen Beweis im Rahmen der Bass-Serre-Theorie.

Satz von Leighton

Bearbeiten

Wenn zwei endliche Graphen eine gemeinsame Überlagerung haben, dann haben sie eine gemeinsame endliche Überlagerung.

Literatur

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