Skip to main content
Article
A Note on the Path Cover Number of Regular Graphs
Australasian Journal of Combinatorics (2009)
  • Colton Magnant, Georgia Southern University
  • Daniel M. Martin
Abstract

Let G be a simple graph of order n. The path cover number μ(G) is defined to be the minimum number of vertex disjoint paths required to cover the vertices of G. Ore proved that in general μ(G) ≤ max{1, n −σ2(G)}. We conjecture that if G is k-regular, then μ(G)n/(k+1) and we prove this for k ≤ 5.

Keywords
  • k-regular
Disciplines
Publication Date
2009
Citation Information
Colton Magnant and Daniel M. Martin. "A Note on the Path Cover Number of Regular Graphs" Australasian Journal of Combinatorics Vol. 43 (2009)
Available at: http://works.bepress.com/colton_magnant/12/