Skip to main content
A Note on the Path Cover Number of Regular Graphs
Australasian Journal of Combinatorics (2009)
  • Colton Magnant, Georgia Southern University
  • Daniel M. Martin, Emory University
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.
  • k-regular
Publication Date
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) p. 211 - 217 ISSN: 1034-4942
Available at: