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.