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 $X subseteq V$ the number of isolated vertices of G − X is at most $m|X|+{rm max}{0,|X| - 1}$ —unless we have the exceptional case of $G simeq K_3$ 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.