오수일 Archives - Page 2 of 2 - KAIST Discrete Math Seminar KAIST Discrete Math Seminar 
 Suil O ( 오수일 ) , Path Cover Number in 4 - regular Graphs and Hamiltonicity in Connected Regular Graphs 
 Path Cover Number in 4 - regular Graphs and Hamiltonicity in Connected Regular Graphs 
 Department of Mathematics , The College of William and Mary , Williamsburg , Virginia , USA 
 2012 / 5 / 16 Wed 4 PM 
 A path cover of a graph is a set of disjoint paths such that every vertex in the graph appears in one of the paths . We prove an upper bound for the minimum size of a path cover in a connected 4 - regular graph with n vertices , confirming a conjecture by Graffiti . pc . We also determine the minimum number of vertices in a connected k - regular graph that is not Hamiltonian , and we solve the analogous problem for Hamiltonian paths . 
 This is a partly joint work with Gexin Yu and Rui Xu . 
 Suil O ( 오수일 ) , Usage of Balloons in Regular Graphs 
 Usage of Balloons in Regular Graphs 
 2011 / 5 / 26 Thu 27 Fri 4 PM - 5 PM ( 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 .