Suil O
College of William & Mary

Balloons and Eigenvalues in Regular Graphs

Abstract: Petersen proved that every cubic graph without cut-edges has a perfect matching, but some graphs with cut-edges have no perfect matching. The smallest cubic graph with no perfect matching belongs to a general family applicable to many problems on connected d-regular graphs with n vertices. These include the smallest matching number for such graphs, and relationships between the eigenvalues and the matching number and between eigenvalues and edge-connectivity in regular graphs.

This is partly joint work with Sebastian M. Cioaba and Doulgas B. West.