0
$\begingroup$

I know given a degree sequence of n vertices, we may find multiple nonisomorphic trees. So the question is how can we find such degree sequences of n vertices that only determine a unique unlabelled tree?

$\endgroup$
0
$\begingroup$

a degree sequence with just one vertex of degree above 1 is such a tree. same for a sequence with only two vertices of degree above 1, these will have to be neighbors in the tree and the rest are just leaves so only one way of setting them up. for three vertices of degree above 1 or more, if they all have the same degree then they can only form one unique path in the tree so that also works. however if at least one of them has a degree different than the others, you can create non-isomorphic variants by deciding whether to use that unique vertex to connect the two other vertices or use some other vertex for that. for four vertices of degree above 1 you can create non-isomorphic variants by deciding whether to connect them as a length-4 path or as a single vertex connecting the three others, the only exception to that rule is if all these vertices are of degree 2, which means they must form a path, this would work for arbitrary amount of vertices as long as non has degree above 2.

I think that sums them all.

$\endgroup$
  • $\begingroup$ Thank you Fuseques! So as you explained, it's trivial when the number of vertices with degree above 1 is less than 3, then for this number >=3, is it equivlaent to say that the condition for such a degree sequence that determines a unique tree is that the degree of those non-leaf vertices should be the same? $\endgroup$ – Panni Oct 9 at 19:55
  • $\begingroup$ not for >=3, only for exactly 3. with 4 or more you get non-isomorfic variants regardless unless all the degrees are 2 or less (it is the last statement of my explanation) $\endgroup$ – Fuseques Oct 10 at 3:08
  • $\begingroup$ Ah right! I think those are all the exceptions. Many thanks! $\endgroup$ – Panni Oct 11 at 16:02

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.