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.