Enumeration of Unigraphical Partitions

Michael D. Hirschhorn School of Mathematics UNSW Sydney 2052 Australia

                   m.hirschhorn@unsw.edu.au

James A. Sellers Department of Mathematics The Pennsylvania State University University Park, PA 16802 USA

                     sellersj@math.psu.edu

Abstract In the early 1960s, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers d_{1}, d_{2}, …, d_{n} to be the degree sequence of a unique graph (that is, one and only one graph realization exists for such a degree sequence). Our goal in this note is to utilize Hakimi’s characterization to prove a closed formula for the function d_{uni}(2m), the number of “unigraphical partitions” with degree sum 2m.

1 Introduction and Statement of Results

In this note, all graphs G = (V, E) under consideration will be finite, undirected, and loopless but may contain multiple edges. We denote the degree sequence of the vertices v_{1}, v_{2}, …, v_{n} by d_{1}, d_{2}, …, d_{n} with the convention that d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n}. We will say that a degree sequence d_{1}, d_{2}, …, d_{n} is unigraphical if there is one and only one graph which realizes this degree sequence. We will also refer to such a degree sequence as a unigraphical partition.

In the early 1960s, S.L. Hakimi [2, 3], characterized those degree sequences which are unigraphical. His results are the following:

Theorem 1. Let 1 ≤ d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} be integers. Then there exists a unique graph with degree sequence d_{1}, d_{2}, …, d_{n} if and only if

• d_{1} + d_{2} + ⋯ + d_{n} is even and

• d_{1} + d_{2} + d_{3} + ⋯ + d_{n−1} ≥ d_{n} and at least one of the following conditions is satisfied: (A) d_{1} + d_{2} + ⋯ + d_{n−1} = d_{n}, (B) n ≤ 3, (C) d_{1} + d_{2} + … d_{n−1} = d_{n} + 2 and d_{1} = d_{2} = ⋯ = d_{n−1}, (D) d_{i} = 1 for i = 1, 2, …, n − 1 (E) n = 4, d_{1} = 1, and d_{2} = d_{3} = d_{4} ≠ 1,

Note that the first two criteria above are necessary for a sequence 1 ≤ d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} to be realizable by some graph [2, Theorem 1], while the last five criteria are specific to the realization of a sequence 1 ≤ d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} as the degree sequence of a unique graph [3, Theorem 5].

In this brief note, we use Theorem 1 to enumerate all unigraphical degree sequences of sum 2m, the number of which we denote by d_{uni}(2m). Our ultimate goal is to prove the following: Theorem 2. For all m ≥ 3,

d_{uni}(2m) = p(m) + ⟨\frac{m^{2}}{12} ⟩ + τ(m + 1) + m − 3 + f(m)

where p(m) is the number of unrestricted integer partitions of m (\underline{A000041}), ⟨\frac{m^{2}}{12} ⟩ is the nearest integer to \frac{m^{2}}{12} (\underline{A001399}), τ(m + 1) is the number of divisors of m + 1 (\underline{A000005}), and f(m) is given by

f(m) = \begin{cases}0 & if m ≡ 0 (mod 6); \\ −1 & if m ≡ 1 (mod 6); \\ 1 & if m ≡ 2 (mod 6); \\ −1 & if m ≡ 3 (mod 6); \\ 0 & if m ≡ 4 (mod 6); \\ 0 & if m ≡ 5 (mod 6). \end{cases}

Moreover, d_{uni}(2) = 1 and d_{uni}(4) = 3.

The techniques necessary for proving Theorem 2 are elementary and follow from a careful analysis of the cases described in Theorem 1.

An example may be beneficial at this time before we proceed to the proof below. In the case m = 4, Theorem 2 yields

d_{uni}(8) = p(4) + ⟨\frac{4^{2}}{12}⟩ + τ(4 + 1) + 4 − 3 + f(4)
= 5 + 1 + 2 + 4 − 3 + 0
= 9.

Thus, there are 9 unigraphical partitions of the integer 8. Below we give each of these partitions along with their unique graph realization.

• •

4 + 4

• • •

4 + 3 + 1

• • •

4 + 2 + 2

• •

•
•

4 + 2 + 1 + 1

• •

•
•

•

4 + 1 + 1 + 1 + 1

• • •

3 + 3 + 2

• •

•
•

• •

3 + 1 + 1 + 1 + 1 + 1

• • •
• •

• •

2 + 1 + 1 + 1 + 1 + 1 + 1

•

•
•

•
•

•
•

•

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 Proof of the Main Result

Proof. It is easy to check that d_{uni}(2) = 1 and d_{uni}(4) = 3. Now suppose m ≥ 3. Our proof of Theorem 2 follows by enumerating the degree sequences which fit into each of the five categories in Theorem 1 and then removing those that have been counted multiple times. We begin now with this case–by–case enumeration.

Case (A): In this case, since d_{1} + d_{2} + ⋯ + d_{n} = 2m and d_{1} + d_{2} + ⋯ + d_{n−1} = d_{n}, we know that d_{1} + d_{2} + ⋯ + d_{n−1} is a partition of m with no restrictions on the parts. Thus, p(m) enumerates the partitions counted by Case (A).

Case (B): We postpone this case briefly.

Case (C): We begin this case by noting that n cannot be 2 as this would imply that d_{1} > d_{2}. Next, note that 2m = 2d_{n} + 2 in this case or d_{n} = m − 1. This means that d_{1} = d_{2} = ⋯ = d_{n−1} = \frac{m+1}{n−1}. Lastly, we see that every divisor n − 1 of m + 1, other than the divisor 1, will generate a new unigraphical partition. (The divisor n − 1 = 1 is excluded since n ≠ 2.) Therefore, the number of unigraphical partitions enumerated in this case is τ(m + 1) − 1.

Case (D): Since d_{1} + d_{2} + ⋯ + d_{n−1} ≥ d_{n}, we know that d_{n} ≤ m. With the only additional restriction that d_{1} = d_{2} = ⋯ = d_{n−1} = 1, we then see that all partitions of the form d_{n} + 1 + 1 + ⋯ + 1 with 1 ≤ d_{n} ≤ m will be unigraphical. Hence, there are m such partitions counted in this case.

Case (E): In this case, the partitions in question are of the form d + d + d + 1 = 2m, so 2m ≡ 1 (mod 3), and 2m is even. Therefore, 2m ≡ 4 (mod 6) which is equivalent to m ≡ 2 (mod 3). Thus, there is exactly one such partition in this case for each m ≡ 2 (mod 3).

It is more convenient to enumerate those partitions in (B) \ (A) than those in (B) directly. The partitions in (B) \ (A) satisfy 1 ≤ d_{1} ≤ d_{2} ≤ d_{3} < d_{1} + d_{2}, which means d_{1}, d_{2}, d_{3} form the sides of a (non–degenerate) triangle of perimeter 2m. The number of such triangles is

⟨\frac{m^{2}}{12} ⟩ . See [1, 4] for more details.

Next, we must consider intersections of the five cases in order to find any partitions that have been counted multiple times. Note that the intersections (A) ∩ (C), (A) ∩ (E), (B) ∩ (D), (B) ∩ (E), (C) ∩ (E), and (D) ∩ (E) are all empty. Next, we consider the intersection (A) ∩ (D). This intersection consists of the one partition with d_{m+1} = m and d_{1} = d_{2} = ⋯ = d_{m} = 1. In a similar fashion, (C) ∩ (D) also consists of one partition, namely d_{m+2} = m − 1 and d_{1} = d_{2} = ⋯ = d_{m+1} = 1. (B) ∩ (C) consists of those partitions

of the form d + d + (2d − 2) = 2m which implies d = \frac{m + 1}{2}. Thus, (B) ∩ (C) contains one partition if m is odd and no partitions if m is even.

Finally, it is easy to check that there are no triple intersections as m ≥ 3, which means we have now covered all possible cases.

Combining all of the analysis above, we see that

d_{uni}(2m) = p(m) + ⟨\frac{m^{2}}{12} ⟩ + τ(m + 1) + m − 3 + f(m)

as defined above.

3 Closing Thoughts

We close by noting that the function f(m) which appears in Theorem 2 is surprisingly related to Sloane’s sequence \underline{A083039}. Indeed, f(m) + 2 = A083039(m − 2) for all m ≥ 3.

4 Acknowledgements

The first author gratefully acknowledges the Penn State University Department of Mathematics for generous support via its Shapiro Fund which allowed him to visit the university during the months of August and September, 2008, when this work was undertaken.

References

[1] G. E. Andrews, A note on partitions and triangles with integer sides, Amer. Math. Monthly 86 (1979), 477.

[2] S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I, J. Soc. Indust. Appl. Math. 10 (1962), 496–506.

[3] S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. II. Uniqueness, J. Soc. Indust. Appl. Math. 11 (1963), 135–147.

[4] M. D. Hirschhorn, Triangles with integer sides, Math. Mag. 76 (2003), 306–308.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A17, 05C75, 11P81. Keywords: partition, degree sequence, graph, unigraphical, generating function

(Concerned with sequences \underline{A000005}, \underline{A000041}, \underline{A001399}, and \underline{A083039}.)

Received September 6 2008; revised version received October 8 2008. Published in Journal of Integer Sequences, October 18 2008.

Return to Journal of Integer Sequences home page.