KAIST Discrete Math Seminar

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.

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.