Suil O (오수일), Usage of Balloons in Regular Graphs

Usage of Balloons in Regular Graphs
Suil O (오수일)
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA
2011/5/26 Thu 27 Fri 4PM-5PM (Room 3433)
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 a relationship between the eigenvalues and the matching number. In addition to these results, we present new results involving this family and the Chinese Postman Problem and a relationship between eigenvalues and edge-connectivity in regular graphs.
This is partly joint work with Sebastian M. Cioaba and Doulgas B. West.


Comments are closed.