Path Cover Number in 4-regular Graphs and Hamiltonicity in Connected Regular Graphs

Suil O (오수일)

Department of Mathematics, The College of William and Mary, Williamsburg, Virginia, USA

Department of Mathematics, The College of William and Mary, Williamsburg, Virginia, USA

2012/5/16 Wed 4PM

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.

This is a partly joint work with Gexin Yu and Rui Xu.