Packing Tree Degree Sequences

Abstract

Special cases of the edge disjoint realizations of two tree degree sequences are considered in this paper. We show that if there is no node which have degree one in both degree sequences, then they always have edge-disjoint caterpillar realizations. By using a probabilistic method, we prove that two tree degree sequences always have edge-disjoint realizations if each vertex is a leaf in at least one of the trees. We also show that the edge-disjoint realization problem is in P for an arbitrary number of tree sequences with the property that each vertex is a non-leaf in at most one of the trees. On the other hand, we show that the following problem is already NP-complete: given two graphical degree sequences D-1 and D-2 such that D-2 is a tree degree sequence, decide if there exist edge-disjoint realizations of D-1 and D-2 where the realization of D-2 does not need to be a tree. Finally, we show that efficient approximations for the number of solutions as well as an almost uniform sampler exist for two tree degree sequences if each vertex is a leaf in at least one of the trees.