Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to determine, given an $N$ and a non-increasing sequence $(a_i)_{i=1}^k$ where $k \leq N$, if a graphic sequence $(d_i)_{i=1}^N$ exists containing $(a_i)$ as a subsequence? Is it further possible to construct one such graphic sequence if any should exist?

For example, for $N = 5$, given the sequence $(4,2,1)$, we can "complete" this as the graphic sequences $(4,2,2,1,1)$ or $(4,3,2,2,1)$, but obviously no such completion exists for the sequence $(4,0)$.

I suppose a brute-force method would be to enumerate all possible degree sequences containing the subsequence, and then checking each if they satisfy the Erdős–Gallai theorem, but for the particular problem I am working on $N$ is quite large and $k$ relatively small, so this is not feasible.

Thanks everyone!

share|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.