Usage of Balloons in Regular Graphs

Suil O (오수일)

Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA

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.

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

Tags: 오수일