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!

Improve this question
$\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$
    – Gerhard Paseman
    Commented Jan 30, 2017 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$
    – Brendan McKay
    Commented Jan 30, 2017 at 6:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .