Satz von Leighton

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

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

Literatur

• 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.

Weblinks

• Walter D. Neumann: On Leighton’s graph covering theorem (Arxiv 2010) (englisch, PDF-Datei; 210 kB)