A tree is arbitrarily vertex decomposable (AVD) if, for every list of positive integers summing to its order, its vertices can be partitioned into connected sets of those sizes. Write for the star-like tree whose arms have those orders, each counting the common central vertex. We prove both conjectures in §4 of Horňák and Woźniak's paper.
- Every admissible sequence gives an AVD tree .
- If both and are admissible, then is AVD.
Admissibility is the conjunction of the five tests of Theorem 12 for every indicated modulus. The proof below uses only tests 1, 2 and 5. We use Theorems 9 and 10, which quote the reductions of Barth and coauthors, and use the numbering of the publicly available preprint throughout. Original preprint · Published paper
1. Packing pieces of two consecutive sizes
Fix positive integers and . When one part of size contains the central vertex, every other part fits in a single arm. Conversely, if all the other parts can be assigned to the arms without exceeding their capacities, place them on consecutive segments starting at the leaves. The unused initial segments, together with the centre, form the central part.
Let denote the available capacity of arm . Write
If pieces of size go in arm , the number of size- pieces it can still accommodate is
The ceiling is nonnegative. To place pieces of size and pieces of size outside the centre, we need , , and total ceiling cost at most . For let be the largest obtainable with that cost budget. At cost zero each arm contributes possible pieces. Each unit of additional cost in that arm increases this allowance by until it reaches , with a possibly smaller final increment. Thus is obtained by taking the largest available increments, including zero increments as needed. Ties can be ordered by taking earlier increments of an arm first. Removing pieces preserves the cost bound. Consequently the assignment exists exactly when and , and
For a fixed total size of the pieces outside the centre, increasing by decreases by and increases by one. By (1), if the largest possible is feasible in the given capacities, so is every smaller for which .
We will also use the complementary count. If pieces of size go in arm , its remaining capacity for pieces of size is
For a partition with , each flooring term is either zero or one. Producing a carry of one in arm requires exactly of the smaller pieces as a minimum, and is possible if . If these minima for the required carries fit within and , the rest of the smaller pieces can be distributed within the remaining space for size . This can only increase the sum of the flooring terms in (2).
2. Partitions without a smaller extra part
Let the arm capacities be their full orders minus one, and let . Let represent modulo . For a modulus let be the quotient on dividing the sum of the arm residues modulo by , so this sum equals . The first admissibility test gives for every index needed in Theorems 9 and 10. We also have in the same range. At the upper endpoint , the two shorter regular arms contribute , the possible one-edge arm contributes one, and the longest arm contributes at most .
Suppose a partition into sizes with at least one size- part exists. Reserve one of the latter for the centre. Among these partitions the smallest possible is and the corresponding budget is . All budgets are therefore nonnegative, so (1) reduces the problem to the partition with the largest . At that endpoint
The nonnegative budget implies that . If , (2) permits the required number of size- parts for any assignment of the size- parts. If , condition 5 of Theorem 12 applies, since this partition has . It gives an arm with and . By (2), put at least smaller pieces there to produce one carry. This accommodates all parts of the endpoint partition, proving the claim for every partition in this class.
3. Three regular arms and one smaller extra part
Here and we have three regular arm capacities , each at least . Write , where for a tripod and when an extra one-edge arm stays with the centre. Suppose there is a part of size with in addition to the parts of sizes . We will reserve size for the centre, including the one-edge arm if present, and place size in a regular arm. Superscript primes will indicate the capacities, quotients, and residues after subtracting from that arm.
Set and , with sums over the three regular arms. The admissibility tests on the residues at and give
Indeed, tests 1 and 2 at a modulus say that the sum of the arm residues other than a largest is less than . For four arms and , the residue of the one-edge arm is 1. A largest residue can be taken among the three regular arms unless they are all zero, in which case the corresponding inequality in (3) holds directly. Both and lie within the admissibility test range when there is a smaller extra part in Theorems 9 and 10.
For each regular arm set and . Then
In particular , and the arm can produce a carry in (2) exactly when , by the identity
Define . When , the partition without with the largest count of size- parts has smaller parts and bigger parts including the centre. It exists precisely when . When it exists, Section 2 and (2) show that there is an arm with
All size- and size- parts outside the centre of that partition belong to regular arms, so the existence of an optional one-edge arm does not change (5).
The endpoint with the most size- parts
For fixed , assume at least one partition in the required class exists. At the endpoint with the largest count of size- parts, put
Here , , and by (3) and . If goes in arm , its size- quotient decreases by exactly when . Thus (2) needs at least carries. Write . Existence of the partition gives .
Case . All . Subtracting from any arm leaves at least slots for the size- parts, since . No carry is needed.
Case . We have . If some , put there, leaving , so there are at least slots for the size- parts and no carry is needed. Suppose all . We will find an arm with and . Subtracting there leaves , and the wrapped size- residue is . The new carry costs smaller parts. This many fit in the arm because . Thus (2) gives feasibility.
To find such an arm, if and , use (5). In the other cases, suppose no arm satisfies both bounds. Every arm with then has . If an arm has , then and , giving . Hence for all arms, so . We have
By (3), there is an arm with , so this arm must have . The other two residues sum to at least , and each is at most . Each is thus at least . The other two residues are at least their corresponding residues, as in all arms. Every pair of residues now sums to at least , contradicting (3). This proves the required existence.
Case . Now and . Since , the partition without at exists. Take the arm from (5). If an arm other than has , place there and produce the required carry in arm at cost . The arm receiving still has room for smaller parts, and , so the total room for smaller parts is at least . If , we may instead place in arm : it has , still has a carry by (4), and its carry costs . Again there is room for at least smaller parts.
In the remaining case the other two arms have and . If another arm has , put there. Arm can produce its usual carry and the adjusted arm can produce a carry at cost , as in the case . Both are needed because . Their total cost is at most , since
for the remaining arm , whose . There is still room for at least smaller parts. Finally, if neither other arm has , we have on both and . But implies
This would force by (3). All possibilities have now been covered, proving feasibility at the largest count of size- parts.
The endpoint with the fewest size- parts
Put . At the endpoint with the smallest count of size- parts, the count outside the centre is . The budget after placing in arm is
This follows by using in the budget formula. By (3), . If , the budget is nonnegative for every choice of arm. The largest-count partition and (1) then give every partition for this . If , only the first endpoint still needs a proof, since every later budget is at least zero for any placement of .
Suppose . Since , (3) gives . Choose an arm with , so and . At this budget we can place bigger pieces. The difference between this number and comes only from the arms with . More precisely, the number of bigger pieces possible is
because . It suffices to make the sum of the indicated at most .
Placing in an arm with leaves unchanged and increases by one if , leaving it unchanged otherwise. If at least two were positive before the placement, at most one is zero. In a zero arm , as required.
Suppose only arm originally had positive . The two other residues satisfy . For this follows from . For we have , so (5) applies and its carry arm must be . If the placement of increases the number of positive arms, the preceding argument applies. Otherwise, the residue in any arm other than receiving decreases, and the required bound on the two zero arms persists.
If all three were zero, choose an arm with largest . When this becomes positive, the two unaltered residues off that arm satisfy and have sum at most by (3). When all three remain zero, in each arm, so the number of bigger pieces possible at zero cost is . This last case also gives feasibility. We have proved the first endpoint, and hence all partitions with the extra part.
4. Applying the reductions
For the tripod, take and . Theorem 9 reduces AVD to the partitions from Section 2 for and those from Section 3 for . In the latter range all arms have capacity at least . Sections 2 and 3 therefore prove Conjecture 1 for every admissible triple.
For the four-arm tree, the shorter sequence is admissible, so its tree is AVD by Conjecture 1. Theorem 10 then reduces AVD of to the same two kinds of partitions, now with in place of in the smaller-extra-part range and upper bound for Section 2. For Section 3 take and capacities . All regular arms have capacity at least in the range in question. This proves Conjecture 2. The proof applies throughout the original ranges and uses no lower bound on the middle arm.
Theorem 12 gives necessity of tests 1, 2 and 5. In the four-arm case, the necessity of decomposability of the remaining tripod follows from Theorem 10. Together with the proof above, the three tests characterize AVD for tripods, and characterize AVD for four-arm trees with a one-edge arm when also applied to the tripod obtained by removing that leaf.