DIMACS TR: 2000-23

How Many Disjoint 2--edge Paths Must a Cubic Graph Have?

Authors: Alexander Kelmans and Dhruv Mubayi


In this paper we show that every simple cubic graph on $n$ vertices has a list of at least n/4 disjoint 2-edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a list in a simple cubic graph.

Keywords: packing, 2--edge path, cubic graph, polynomial time algorithm.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-23.ps.gz
DIMACS Home Page