¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 79-84
An improvement of a result of Zverovich-Zverovich
Grant Cairns *, Stacey Mendan
Department of Mathematics and Statistics, La Trobe University, Melbourne, Australia 3086
Received 8 March 2013, accepted 20 October 2013, published online 27 May 2015 Abstract
We give an improvement of a result of Zverovich and Zverovich which gives a condition on the first and last elements in a decreasing sequence of positive integers for the sequence to be graphic, that is, the degree sequence of a finite graph.
Keywords: Graph, graphic sequence. Math. Subj. Class.: 05C07
1 Statement of Results
A finite sequence of positive integers is graphic if it occurs as the sequence of vertex degrees of a graph. Here, graphs are understood to be simple, in that they have no loops or repeated edges. A result of Zverovich and Zverovich states:
Theorem 1.1 ([8, Theorem 6]). Let a, b be reals. If d = (di,...,dn) is a sequence of positive integers in decreasing order with di < a,dn > b and
(1 + a + b)2
n >
4b
then d is graphic.
Notice that here the term (i+4+b) is monotonic increasing in a, for a > 1 and fixed b, and it is also monotonic decreasing in b, for a > b > 1 and fixed a. Thus any sequence that satisfies the inequality n > (i+a+b) , for any pair a > di,b < dn, will also satisfy the inequality n > (i+'41(+dn) . So Theorem 1.1 has the following equivalent expression.
* Corresponding author
E-mail addresses: G.Cairns@latrobe.edu.au (Grant Cairns), spmendan@students.latrobe.edu.au (Stacey Mendan)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
80
Ars Math. Contemp. 10 (2016) 99-112
Theorem 1.2. Suppose thatd = (di,..., dn) is a decreasing sequence of positive integers with even sum. If
n > (1 + di + dn)2 ,	(1.1)
4dn
then d is graphic.
The simplified form of Theorem 1.2 also affords a somewhat simpler proof, which we give in Section 2 below. Admittedly, the proof in [8] is already quite elementary, though it does use the strong index results of [4, 3].
The following corollary of Zverovich-Zverovich's is obtained by taking a = di and b =1 in Theorem 1.1.
Corollary 1.3 ([8, Corollary 2]). Suppose that d = (di,..., dn) is a decreasing sequence of positive integers with even sum. If di < 2n 2 — 2, then d is graphic.
Note that this can be expressed in the following equivalent form.
Corollary 1.4. Suppose thatd = (di,..., dn) is a decreasing sequence of positive integers
d2
with even sum. If n > -4 + di + 1, then d is graphic.
Zverovich-Zverovich state that the bound of Corollary 1.4 "cannot be improved", and they give examples to this effect. In fact, there is an improvement, as we will now describe. The subtlety here is that Zverovich-Zverovich formulated their result as an upper bound on di, and, as an upper bound on di, this upper bound on di cannot be improved. However, the reformulation of their result as a lower bound on n can be slightly improved. We prove the following result in Section 2.
Theorem 1.5. Suppose thatd = (di,..., dn) is a decreasing sequence of positive integers
-2
4
-2
with even sum. If n > -h + di , then d is graphic.
Example 1.6. There are many examples of sequences that verify the hypotheses of Theorem 1.5 but not those of Corollary 1.4. In fact, there are 81 such sequences of length n < 8. Figure 1 shows three graphs whose degree sequences have this property; they have degree sequences (2, 2,2), (3, 3, 2,2,2) and (3, 3,3,3, 3, 3) respectively. For infinite families of examples, for every positive odd integer x, consider the sequence (2x, 1x +2x-i), and for x even, consider the sequence (2x, 2x, 1x +2x-2). Here, and in sequences throughout this paper, the superscripts indicate the number of repetitions of the entry.
Example 1.7. The following examples show that the bound of Theorem 1.5 is sharp when
dn = 1. For d even, say d = 2x with x > 1, let d = (dx+i, 1x +x-2). For d odd, say d = 2x + 1 with x > 1, let d = (dx+i, 1x +2x-i). In each case g has even sum, — 1, but d is not graphic, as one can see from the Erdos-Gallai Theorem [6].
-42+d
Remark 1.8. The fact that Theorem 1.2 is not sharp has also been remarked in [1], in the abstract of which the authors state that Theorem 1.2 is "sharp within 1". They give the bound
n > (1 + di + dn)2 — e',	(1.2)
>	4dn	,	^ '
Grant Cairns and Stacey Mendan: An improvement of a result ofZverovich-Zverovich
81
A
Figure 1: Three examples
where e' = 0 if di + dn is odd, and e' =1 otherwise. Consider any decreasing sequence with di = 2x+1 and dn = 1. Note that the bound given by Theorem 1.2 is n > x2+3x+3, the bound given by (1.2) is n > x2 + 3x + 2, while Theorem 1.5 gives the stronger bound n > x2 + 3x +1. The paper [1] gives more precise bounds, as a function of di; dn, and the maximal gap in the sequence.
Remark 1.9. There are many other recent papers on graphic sequences; see for example [5, 7, 1, 2].
2 Proofs of Theorems 1.2 and 1.5
We will require the Erdos-Gallai Theorem, which we recall for convenience.
Erdos-Gallai Theorem. A sequence d = (di,..., dn) of nonnegative integers in decreasing order is graphic if and only if its sum is even and, for each integer k with 1 < k < n,
k	n
^ di < k(k - 1) + ^ min{k, d,}.	(EG)
i=i i = k + i
Proof of Theorem 1.2. Suppose that d = (di;..., dn) is a decreasing sequence with even sum, satisfying (1.1), and which is not graphic. By the Erdos-Gallai Theorem, there exists k with 1 < k < n, such that
kn
^ di > k(k - 1)+ ^ min{k,di}.	(2.1)
i=i i=k + i
For each i with 1 < i < k, replace d, by di; the left hand side of (2.1) is not decreased, while the right hand side of (2.1) is unchanged, so (2.1) still holds. Now for each i with k + 1 < i < n, replace d, by dn; the left hand side of (2.1) is unchanged, while the right hand side of (2.1) has not increased, so (2.1) again holds. Notice that if k < dn, then (2.1) gives kdi > k(k - 1) + (n - k)k = k(n - 1), and so di > n. Then (1.1) would give 4ndn > (1+dn+n)2, that is, (n-(dn-1))2-(dn-1)2 + (1+dn)2 < 0. But this inequality clearly has no solutions. Hence k > dn. Thus (2.1) now reads kdi > k(k - 1) + (n - k)dn, or equivalently
(k - ^(1 + di + dn))2 - 4(1 + di + dn)2 + ndn < 0.
82
Ars Math. Contemp. 10 (2016) 99-112
But this contradicts the hypothesis.	□
The following proof uses the same general strategy as the preceding proof, but requires a somewhat more careful argument.
Proof of Theorem 1.5. Suppose that d satisfies the hypotheses of the theorem. First suppose
that di is even, say di = 2x. If dn > 2, then since (1+-4--+dl) is a strictly monotonic decreasing function of dn for 1 < dn < d1, we have
^ d1	(2 + di)2 1	(1+ dn + di)2
n > T + di = -;--1 > -71--1,
4	4	4dn
n
so n > (i+'4'+dl) and hence d is graphic by Theorem 1.2. So, assuming that d is not graphic, we may suppose that dn = 1. Furthermore, by Corollary 1.4, we may assume that
n = "j- + di, so n = x2 + 2x.
4
Now, as in the proof of Theorem 1.2, by the Erdos-Gallai Theorem, there exists k with 1 < k < n, such that
k	n
^dj > k(k - 1) + min{k,dj}.	(2.2)
j=1 j=k + 1
For each i with 1 < i < k, replace dj by di; the left hand side of (2.2) is not decreased, while the right hand side of (2.2) is unchanged, so (2.2) still holds. For each i with k + 1 < i < n, replace dj by 1; the left hand side of (2.2) is unchanged, while the right hand side of (2.2) has not increased, so (2.2) again holds. Then (2.2) reads kdi > k(k - 1) + (n - k), and consequently, rearranging terms, (k - x -1)2 -1 < 0. Thus k = x + 1. Notice that for 1 < i < k, if any of the original terms dj had been less than di, we would have obtained (k - x - 1)2 < 0, which is impossible. Similarly, for k + 1 < i < n, all the original terms dj must have been all equal to one. Thus d = (dk, 1n-k) = ((2x)x+i, 1x +x-i). So d has sum 2x(x + 1) + x2 + x - 1 = 3x2 + 3x - 1, which is odd, regardless of whether x is even or odd. This contradicts the hypothesis.
Now consider the case where di is odd, say di = 2x - 1. The theorem is trivial for d = (1n), so we may assume that x > 1. We use essentially the same approach as we used in the even case, but the odd case is somewhat more complicated. By Corollary 1.4, assuming d is not graphic, we have +di+1 > n, and hence, as di is odd, "J- +di+4 > n.
Thus, since n > Thus there are two cases:
"J + di
41 u-1 I i ^	uo U-1	4 I «a I 4
= -4 + di - 4, we have n = ^ + di + 3 or n = + di - 4.
(i)	n = x2 + x - 1,
(ii)	n = x2 + x.
By the Erdos-Gallai Theorem, there exists k with 1 < k < n, such that
kn
^ dj > k(k - 1)+ ^ min{k,dj}.	(2.3)
j=i j=k+i
As before, for each i with 1 < i < k, replace dj by d1 and for each i with k + 1 < i < n, replace dj by dn, and note that (2.3) again holds. Arguing as in the proof of Theorem 1.2,
Grant Cairns and Stacey Mendan: An improvement of a result ofZverovich-Zverovich
83
notice that if k < dn, then (2.3) gives kdi > k(k — 1) + (n — k)k = k(n — 1), and so d1 > n. In both cases (i) and (ii) we would have 2x — 1 > n > x2 + x — 1 and hence x < 1, contrary to our assumption. Thus k > dn and (2.3) reads kdi > k(k — 1) + (n — k)dn, and consequently, rearranging terms, we obtain in the respective cases:
(i)	dnx2 — dnk + k2 + dnx — 2kx — dn < 0.
(ii)	dnx2 — dnk + k2 + dnx — 2kx < 0,
In both cases we have dnx2 — dnk + k2 + dnx — 2kx — dn < 0. Consider dnx2 — dn k H- k 2 + dnx — 2kx — dn as a quadratic in k. For this to be negative, its discriminant, 4dn + dn + 4x2 — 4dnx2, must be positive. If dn > 1 we obtain x2 < ^¿"—f). For dn = 2 we have x2 < 3 and so x =1, contrary to our assumption. Similarly, for dn = 3 we have x2 < 21 and so again x = 1. For dn > 4, the function ^"-i) is monotonic increasing in dn. So, as dn < d1,
2 4d1 + d2 4x2 + 4x - 3 x2 + x x2 < -r-;-rr = -^-^- <
4(d1 — 1) 8x — 8 2(x — 1)'
which again gives x =1. We conclude that dn = 1. So the two cases are:
(i)	x2 — k + k2 + x — 2kx — 1 = (k — x)(k — x — 1) — 1 < 0.
(ii)	x2 — k + k2 + x — 2kx = (k — x)(k — x — 1) < 0,
In case (ii) we must have x < k < x +1, but this is impossible for integer k and x.
In case (i), either k = x or k = x +1. Notice that for 1 < i < k, if any of the original terms dj had been less than d;, we would have obtained (k — x)(k — x — 1) < 0, which is impossible. Similarly, for k + 1 < i < n, all the original terms dj must have been all equal to one. Thus d = (df, 1n-k). Consequently, if k = x, we have d = ((2x — 1)x, 1x -1) as n = x2 + x — 1. In this case, d has sum x(2x — 1) + x2 — 1 = 3x2 — x — 1, which is odd, regardless of whether x is even or odd, contradicting the hypothesis. On the other hand, if k = x + 1, we have d = ((2x — 1)x+1,1x -2). Here, d has sum (2x — 1)(x +1) + x2 — 2 = 3x2 + x — 3, which is again odd, regardless of whether x is even or odd, contrary to the hypothesis.	□
References
[1]	M. D. Barrus, S. G. Hartke, K. F. Jao, and D. B. West, Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps, Discrete Math. 312 (2012), no. 9, 14941501.
[2]	G. Cairns and S. Mendan, Symmetric bipartite graphs and graphs with loops, preprint.
[3]	P. L. Hammer, T. Ibaraki, and B. Simeone, Threshold sequences, SIAM J. Algebraic Discrete Methods 2 (1981), no. 1, 39-49.
[4]	S.Y.R. Li, Graphic sequences with unique realization, J. Combinatorial Theory Ser. B 19 (1975), no. 1,42-68.
[5]	A. Tripathi and H. Tyagi, A simple criterion on degree sequences of graphs, Discrete Appl. Math. 156 (2008), no. 18, 3513-3517.
84
Ars Math. Contemp. 10 (2016) 99-112
[6]	A. Tripathi, S. Venugopalan and D. B. West, A short constructive proof of the Erdos-Gallai characterization of graphic lists, Discrete Math. 310 (2010), no. 4, 843-844.
( r)
[7]	J.-H. Yin, Conditions for r-graphic sequences to be potentially K^+x-graphic, Discrete Math. 309 (2009), no. 21, 6271-6276.
[8]	I. E. Zverovich and V. E. Zverovich, Contributions to the theory of graphic sequences, Discrete Math. 105 (1992), no. 1-3, 293-303.