Short Paths in Regular Graphs
by
Dave Elkin
University of Otago

Habib and Peroché (1982) introduced the following definitions. A linear k-forest is a collection of vertex disjoint paths, each path containing no more than k edges. The linear k-arboricity of G, la_k(G), is the minimum number of linear k-forests required to partition E(G).

We present an introduction to the study of this invariant for regular graphs. Counting arguments allows the establishment of a simple lower bound. Examples of infinite families that realise this bound are given, as well as examples of graphs that don't. Counter examples to two current conjectures on the value of la_k(G) are presented. Relevant results from the study of path designs and chromatic index are discussed. From this a new conjecture for the value of the linear k-arboricity of a regular graph is proposed.

Date received: November 9, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-44.