2
$\begingroup$

A sequence of non-negative integers is graphic if it is the degree sequence of some simple graph. Graph realization problem is the decision problem where it is asked whether a given sequence is graphic or not. Some quick tests one can do include checking that both the sum and sum of squared elements are even. The full solution is known and there are many algorithms one can use.

I recently considered the following related problem: given the length $N$, sum $D$, and sum of squares $A$, find all graphic sequences with these $N$, $D$ and $A$. Surprisingly, some quick brute force testing suggests that if one finds all sequences of length $N$ with sum $D$ and sum of squared elements $A$, then either all or none of them are graphic.

It's easy for me to understand that if, e.g., $D$ or $A$ is odd or if $N A-D^2<0$ then no graphic sequences like this exist, but I'm still surprised how apparently the graphicness of a sequence can be reduced to the graphicness of the triplet $(N,D,A)$. Looking at how complicated the conditions on the elements themselves are in, e.g., Erdős–Gallai theorem, I would not expect that it's enough to simply check tree numbers readily determined from the sequence.

So, my question is:

Can you find a triplet $(N,D,A)$ such that some sequences of non-negative integers with length $N$, sum $D$ and sum of squared elements $A$ are graphic and some are not? Or can you show that there is no in-between, i.e. either all or none of the sequences characterized by $(N,D,A)$ are graphic. If there is no in-between, what is the condition on $(N,D,A)$?

EDIT: The relation to integer partitions is probably a good place to start.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.