The Lovasz Two Ear Theorem and the Enumeration of 1-Extendable Graphs

Meeting Time: Nov. 23, 2010, 2:00-2:50pm

Abstract: In a previous talk, we used the Cathedral Theorem to reduce an extremal problem on saturated graphs to one on elementary graphs. To tackle this case, we again turn to Lovasz and his Two Ear theorem on 1-extendable graphs. We apply this to turn the problem on elementary graphs into a finite problem as well as detail how to exhaustively search for the extremal representatives.