Packing tree degree sequences
A degree sequence is a list of non-negative integers, \(D = d_1, d_2,\dots, d_n\). It is called graphical if there exists a simple graph \(G\) such that the degree of the \(i^{\text{th}}\) vertex is \(d_i\); \(G\) is then said to be a realization of \(D\). A degree sequence \(D = d_1, d_2, \dots, d_n\) is a tree degree sequence if all degrees are positive and \(\sum_{i=1}^n d_i = 2n- 2\). A degree sequence is a path degree sequence if two of its degrees are 1 and all other degrees are \(2\). The paper consideres the problem of packing tree degree sequences: given \(k\) tree degree sequences, do they have simultaneous (i.e. on the same vertices) edge-disjoint realizations? Also it conjectured that this is true for any arbitrary number of tree degree sequences whenever they share no common leaves (degree-1 vertices). This paper gives a proof for \(4\) tree degree sequences and a computer-aided proof for \(5\) tree degree sequences. The conjecture for arbitrary \(k\) is also considered. It is proved that \(k\) tree degree sequences without common leaves and at least \(2k- 4\) vertices which are not leaves in any of the trees always have edge disjoint tree realizations.
- A note on a theorem of Erdős and Gallai
- A short proof of Kundu's k-factor theorem
- A simple criterion on degree sequences of graphs
- Colour degree matrices of graphs with at most one cycle
- Contributions to the theory of graphic sequences
- Degree-constrained edge partitioning in graphs arising from discrete tomography
- Disjoint Representation of Three Tree Realizable Sequences. I
- Disjoint Representation of Tree Realizable Sequences
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- Packing of graphic n-tuples
- Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
- The k-factor conjecture is true
- The wonderful Walecki construction
This page was built for publication: Packing tree degree sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175807)
