A remark concerning graphical sequences

A remark concerning graphical sequences Geir Dahl

Truls Flatberg June 2005 Abstract

In “A note on a theorem of Erd¨ os & Gallai” ([6]) one identifies the nonredundant inequalities in a characterization of graphical sequences. We explain how this result may be obtained directly from a simple geometrical observation involving weak majorization.

A sequence of positive integers d1 , d2 , . . . , dp is called graphical if it is the degree sequence of a graph, i.e., there is a graph whose vertices have degrees d1 , d2 , . . . , dp . Sierksma and Hoogeveen [5] presents several (actually seven) equivalent conditions for an integer sequence to be graphical. For a further discussion of this topic, see Chapter 7 of [3] or Chapter 3 of [4]. One well-known characterization of graphical sequences is the following theorem of Erd¨ os and Gallai [1]. Theorem 1 ([1]) A nonincreasing sequence of positive integers d1 , d2 , . . . , dp is Pp graphical if and only if i=1 di is even and k X

p X

di ≤ k(k − 1) +

i=1

min(k, di )

(k ≤ p).

(1)

i=k+1

A strengthening of this result was given in [6]. The indices 1 ≤ i ≤ p − 1 with di > di+1 are denoted by σ1 , σ2 , . . . , σl−1 , and define σl = p. Theorem 2 ([6]) In Theorem 1 it suffices to check the inequalities (1) for k = σ1 , σ 2 , . . . , σ l . Define K = max{i : di ≥ i}. Similar to [6] we observe that it suffices to check the inequalities (1) for k ≤ K. (The argument here is similar to the one in [6] except that their maximum k might be one larger than K). Let d∗ be the conjugate sequence of d with elements given by d∗k = |{i : di ≥ k}| (and with trailing zeros). This is a nonincreasing sequence. Let k ≤ K. Then the k’th inequality in (1) becomes k X i=1

(di + 1) ≤

k X i=1

1

d∗i

(k ≤ K).

(2)

These inequalities are referred to as the H¨ asselbarth criterion in [5] while [3] attributes this result to Ruch and Gutman; see these papers for the appropriate references. Define sequences d0 and d∗ with elements dk + 1 and d∗k for k = 1, . . . , K respectively. Then the condition (2) says that d0 is weakly majorized by d∗ , denoted by d0 ≺w d∗ . We refer to [2] for a comprehensive treatment of the notion of majorization. Majorization may be interpreted geometrically as follows. Let u be a sequence with nonincreasing elements u1 ≥ u2 ≥ · · · ≥ un . Consider the associPk ated points (k, Uk ) (k = 0, . . . , n) in the plane, where Uk = i=1 uk for k ≥ 1 and U0 = 0. The linear interpolant of these points is called the Lorenz curve associated with u. Since the elements of u are nonincreasing this curve will be concave. If u and v are two nonincreasing sequences, then v is weakly majorized by u if and only if the Lorenz curve of u lies above that of v, see Figure 1. U V

0

1

2

n

Figure 1: Weak majorization geometrically. Due to concavity it suffices to check the majorization condition (Vk ≤ Uk ) at the endpoints of the linear segments (i.e., the breakpoints) of the Lorenz curve associated with v. This is our key observation. We now apply this observation to our original problem and consider the weak 0 ∗ majorization Pσdk ≺0w d . The breakpoints of the Lorenz curve associated with 0 d are (σk , i=1 di ) for k = 1, 2, . . . , l. Therefore Theorem 2 is an immediate consequence of our key observation. Acknowledgments. The authors thank the referees for some useful comments.

References [1] P. Erd¨ os and T. Gallai. Graphs with prescribed degree of vertices. (Hungarian). Mat. Lapok, 11:264–274, 1960. [2] A.W. Marshall and I. Olkin. Inequalities : Theory of Majorization and Its Applications. Academic Press, 1979. 2

[3] R. Merris. Graph Theory. John Wiley & Sons, 2001. [4] U. Peled and N. Mahadev. Threshold Graphs and Related Topics. Annals of Discrete Mathematics 56, North-Holland, 1995. [5] G. Sierksma and H. Hoogeveen. Seven criteria for integer sequences being graphic. J. Graph Theory, 15:223–231, 1991. [6] A. Tripathi and S. Vijay. A note on a theorem of Erd¨ os & Gallai. Discrete Math., 265:417–420, 2003.

3