For my research I am interested in finding disjoint copies of certain "good structures" in graphs which are trees with a perfect matching. So let $T$ be a tree with a perfect matching $M$. I am interested in the following types of good structures:

I) A path on four vertices $(v_1, v_2, v_3, v_4)$ such that vertices $v_1$ and $v_4$ are leaves of the tree (which implies that the edges $\{v_1, v_2\}$ and $\{v_3, v_4\}$ are contained in the matching), and

II) A matching edge $\{v_1, v_2\}$ such that both involved vertices have degree at most two in $T$.

Say that a packing of good structures is simply a set of mutually vertex-disjoint subgraphs of $T$, where each subgraph has structure I or II. The result I am interested in is as follows: for each tree $T$ with a perfect matching on $n$ vertices, there is a packing of at least $n/c$ good structures, for some constant $c$ which is not too large. I can prove the theorem for $c$ about 15 or so by using a technique used by Griggs et al. ( Griggs, J.R., Kleitman, D., Shastri, A.: Spanning trees with many leaves in cubic graphs.) and later Kleitman and West, dubbed "amortized analysis by keeping track of dead leaves", which is used by them to prove lower-bounds on the number of leaves that you can find in spanning trees for certain graphs. The problem is: the proof requires a tedious case analysis. So I am looking for a cleaner way to prove this result, for a constant $c$ which is not bigger. I have tried to come up with an induction to capture what is going on, but to no avail. The problem is that when you find a good structure in a graph, remove it and apply induction on the remainder, then the removal of the good structure will change the degree of its neighboring vertices in the graph that is used for induction. Hence when we find a good structure in the remainder (by induction), they might not be good in the original graph because the degrees lowered by deleting the good structure we were looking at. Any suggestions or pointers to similar results in the literature are much appreciated.

  • $\begingroup$ What (if any) inductive definitions/generations do you have for your class? Gerhard "Watching The Odometer Roll Over" Paseman, 2011.11.07 $\endgroup$ – Gerhard Paseman Nov 7 '11 at 21:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.