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



Abstract

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= K3 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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2007},
NUMBER = {TR-2007-04}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!