5
$\begingroup$

The following theorem about the degree sequences of finite simple graphs is quite easy to prove from the Erdos-Gallai theorem.

Let $0 \lt \alpha \le \beta \lt n$ be integers. Call $(\alpha,\beta,n)$ paragraphical if every integer sequence $\alpha \le d_1,\ldots,d_n \le \beta$ with even sum is the degree sequence of a simple graph. Then $(\alpha,\beta,n)$ is paragraphical iff $$ n \ge \biggl\lfloor\frac{ (\alpha+\beta+1)^2 }{4 \alpha} \biggr\rfloor.$$

I find it really hard to believe that nobody published this anywhere, but can I find it? The question is: where is it?

Thanks!

$\endgroup$
2
  • $\begingroup$ I take it paragraphical is your term and not standard. Any idea what term might be used, or who might have worked on ranges of degree sequences? Gerhard "Not On My Tongue Tip" Paseman, 2017.01.29. $\endgroup$ Jan 30 '17 at 6:13
  • $\begingroup$ @GerhardPaseman: I just made it up for the question. I doubt if there is a standard term. Lots of people worked on degree sequences. $\endgroup$ Jan 30 '17 at 6:47
5
$\begingroup$

Answering my own question: Almost exactly this result was proved in:

Igor E Zverovich and Vadim E Zverovich. Contributions to the theory of graphic sequences. Discrete Mathematics, 105(1):293–303, 1992.

Having now found this, I recall that someone gave me the tip "Zverovich" at a conference last year, but I lost the tip and also forgot who it was that gave it to me (sorry).

An improvement, allegedly the best possible improvement, appeared in G. Cairns, S. Mendan, Y. Nikolayevsky, A sharp refinement of a result of Zverovich–Zverovich, Discrete Mathematics, Volume 338, Issue 7, 6 July 2015, Pages 1085-1089.

The result of Cairns et al. is similar to what is in my question, but not exactly the same. After looking very closely I can see that my version is wrong. The simplest proof is that it is not closed under complementation. My apologies to anyone who tried to prove it.

$\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.