Packing Trees with Constraints on the Leaf Degree

If m is a positive integer then we call a tree on at least 2 vertices an m-tree if no vertex is adjacent to more than m leaves. Kaneko proved that a connected, undirected graph G = (V, E) has a spanning m-tree if and only if for every the number of isolated vertices of G − X is at most —unless we have the exceptional case of and m = 1. As an attempt to integrate this result into the theory of graph packings, in this paper we consider the problem of packing a graph with m-trees. We use an approach different from that of Kaneko, and we deduce Gallai–Edmonds and Berge–Tutte type theorems and a matroidal result for the m-tree packing problem. Jácint Szabó: Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No.504438.