TR-2007-04

Packing trees with constraints on the leaf degree

Jácint Szabó

Published in:
Information Processing Letters Volume 106, Issue 4, 16 May 2008, Pages 149-151

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 an 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|+(|X|-1)⁺ - unless we are at the exceptional case of G= K₃ 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 to that of Kaneko, and we deduce Gallai--Edmonds and Berge--Tutte type theorems and a matroidal result to the m-tree packing problem.

Bibtex entry:

@techreport{egres-07-04,

AUTHOR	=	{Szab{\'o}, J{\'a}cint},
TITLE	=	{Packing trees with constraints on the leaf degree},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2007},
NUMBER	=	{TR-2007-04}

}