0
$\begingroup$

I recently encountered this problem. Frankly I'm stuck; would be nice for some help. Here it is:

Let $N,k$ be positive integers. By $p_k(N)$ we denote the number of integer partitions of $N$ with exactly $k$ parts; that is, the number of ways to write $N$ as a sum of exactly $k$ positive integers, where the order of summands does not matter. What is the number of pairwise non-isomorphic spanning trees of $W_n$ of maximum degree at least 4 and with at most 1 vertex of degree 3? Write this number using terms of the form $p_k(N)$.

$\endgroup$
2
$\begingroup$

A beginning:

You should give your exact definition of a wheel $W_n$, as the notation is inconsistent in the literature.

It is required that the spanning tree $T$ has a vertex of degree $\geq4$, and this has to be the center of the wheel. All other vertices of $T$ have degree $\leq3$, at most one of them degree $3$. The latter can happen only in the following way: One spike emanating from the center bifurcates at its end.

Now draw a few pictures in order to get an overwiew of what is possible. Note that the cyclic arrangement of the spikes is irrelevant when it comes to isomorphy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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