Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a tree with a given root, let $d_i$ be the number of vertices at distance $i$ from the root. Given the distance distribution $d =[d_1, d_2, \cdots, d_k]$ ($k$ is the diameter), how many (non-isomorphic) trees can we construct with the same root?

Further, if we restrict the maximum degree of each vertex to be some constant $c$, how does the count change? Even more, how many connected simple graphs can we construct such that at least one vertex has the distance distribution $d$.

MOTIVATION:
This is a problem in mathematical chemistry or precisely Inverse QSAR. I would chose $c$ to be 4 (maximum valency of atoms). Some function of distance distribution $d$ are used as "descriptor" of molecules (topological indices) and correlation are established between these descriptors and bioactivity. Now the problem is to design molecules (graph representations) that would correspond to the descriptors.

share|improve this question

1 Answer 1

Even with a distinguished root and insisting that all isomorphisms respect this distinguished root, this will be a challenging enumeration.

For $k \leq 2$ the problem is straightforward: The count is the number of partitions of $d_2$ into at most $d_1$ parts. This has an upper bound of $\binom{d_2+d_1 - 1}{d_1 - 1}$, call this quantity $q(d_2,d_1)$, and the literature doubtless has more to say on the exact count. Call this number $p(d_2,d_1)$, and let such a partition be denoted by the vector $(n_1,n_2,\ldots, n_{d_1})$, where the $n_i$ are in decreasing order and sum to $d_2$. To handle $d_3$ will involve a summation over all such partitions of products of terms like $p(k_i,n_i)$, where the $k_i$ sum up to $d_3$. Except it won't be that simple, as you need $k_i$ to be 0 when $n_i$ is 0, and you need to identify certain counts when you have $n_i=n_{i+1}$, and so on. Using $\prod q(d_{i+1},d_i)$ as an upper bound will likely be a weak estimate, unless all the $d$'s are small, and even then I would compare with a computer enumeration.

Of course $n(c,d_2,d_1)$ will often be much smaller than $p(d_2,d_1)$, where this new count restricts the parts $n_i \lt c$, and there should be some literature on $n()$ as well. I still recommend computer enumeration for cases of small diameter.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.