\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{pstricks} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Enumeration of Unigraphical Partitions } \vskip 1cm \large Michael D. Hirschhorn \\ School of Mathematics\\ UNSW\\ Sydney 2052\\ Australia\\ \href{mailto:m.hirschhorn@unsw.edu.au}{\tt m.hirschhorn@unsw.edu.au}\\ \ \\ James A. Sellers\\ Department of Mathematics\\ The Pennsylvania State University\\ University Park, PA 16802\\ USA\\ \href{mailto:sellersj@math.psu.edu}{\tt sellersj@math.psu.edu}\\ \end{center} \vskip .2 in \begin{abstract} In the early 1960s, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers $d_1, d_2, \dots, 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_{\rm uni}(2m),$ the number of ``unigraphical partitions'' with degree sum $2m.$ \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newcommand{\N}[2]{N^{\#}_{#1}(#2)} %\newtheorem{Notation}[Lemma]{Notation} %\newtheorem{Remark}[Lemma]{Remark} %\newtheorem{Table}[Lemma]{Table} %\newtheorem{Definition}[Lemma]{Definition} \renewcommand{\labelenumi}{(\Alph{enumi})} \begin{section}{Introduction and Statement of Results} \label{sec:intro} In this note, all graphs $G = (V,E)$ under consideration will be finite, undirected, and loopless but may contain multiple edges. We denote the {\it degree sequence} of the vertices $v_1, v_2, \dots, v_n$ by $d_1, d_2, \dots, d_n$ with the convention that $d_1 \leq d_2 \leq \dots \leq d_n.$ We will say that a degree sequence $d_1, d_2, \dots, d_n$ is {\it 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 {\it unigraphical partition}. %As usual, a graph is called {\it connected} if it has only one component. We say that a vertex $v$ is a {\it %cut--vertex} of $G$ if $|E(G)| \geq 2$ and $G-v$ has more components than $G.$ A graph is called {\it non--separable} %if it is connected and has no cut--vertices. In the early 1960s, S.L. Hakimi \cite{HAK1, HAK2}, characterized those degree sequences which are unigraphical. His results are the following: \begin{theorem} \label{hakimi_char_unigraphical} Let $1\leq d_1 \leq d_2 \leq \dots \leq d_n$ be integers. Then there exists a unique graph with degree sequence $d_1, d_2, \dots, d_n$ if and only if \begin{itemize} \item{} $d_1+d_2+\dots+d_n $ is even and \item{} $d_1 + d_2+d_3+\dots +d_{n-1} \geq d_n $ \end{itemize} and at least one of the following conditions is satisfied: \begin{enumerate} \item{} $d_1+d_2+\dots + d_{n-1} = d_n,$ \item{} $n\leq 3,$ \item{} $d_1+d_2+\dots d_{n-1} = d_n + 2$ and $d_1=d_2=\dots =d_{n-1},$ \item{} $d_i=1$ for $i=1,2,\dots, n-1$ \item{} $n=4,$ $d_1=1,$ and $d_2=d_3=d_4 \neq 1,$ \end{enumerate} \end{theorem} Note that the first two criteria above are necessary for a sequence $1\leq d_1 \leq d_2 \leq \dots \leq d_n $ to be realizable by some graph \cite[Theorem 1]{HAK1}, while the last five criteria are specific to the realization of a sequence $1\leq d_1 \leq d_2 \leq \dots \leq d_n$ as the degree sequence of a {\bf unique} graph \cite[Theorem 5]{HAK2}. In this brief note, we use Theorem~\ref{hakimi_char_unigraphical} to enumerate all unigraphical degree sequences of sum $2m,$ the number of which we denote by $d_{\rm uni}(2m).$ Our ultimate goal is to prove the following: \begin{theorem} \label{new_unigraphical} For all $m\geq 3,$ $$d_{\rm uni}(2m) = p(m) + \left\langle \frac{m^2}{12} \right\rangle +\tau(m+1) +m - 3 + f(m)$$ where $p(m)$ is the number of unrestricted integer partitions of $m$ (\seqnum{A000041}), $\displaystyle{\left\langle \frac{m^2}{12} \right\rangle}$ is the nearest integer to $\displaystyle{\frac{m^2}{12}}$ (\seqnum{A001399}), $\tau(m+1)$ is the number of divisors of $m+1$ (\seqnum{A000005}), and $f(m)$ is given by \begin{equation*} f(m)= \begin{cases} 0 & \text{if $m\equiv 0\pmod{6}$;} \\ -1 &\text{if $m\equiv 1\pmod{6}$;} \\ 1 &\text{if $m\equiv 2\pmod{6}$;} \\ -1 &\text{if $m\equiv 3\pmod{6}$;} \\ 0 &\text{if $m\equiv 4\pmod{6}$;} \\ 0 &\text{if $m\equiv 5\pmod{6}$.} \end{cases} \end{equation*} Moreover, $d_{\rm uni}(2) =1$ and $d_{\rm uni}(4) = 3.$ \end{theorem} The techniques necessary for proving Theorem~\ref{new_unigraphical} are elementary and follow from a careful analysis of the cases described in Theorem~\ref{hakimi_char_unigraphical}. An example may be beneficial at this time before we proceed to the proof below. In the case $m=4,$ Theorem~\ref{new_unigraphical} yields \begin{eqnarray*} d_{\rm uni}(8) &=& p(4)+\left\langle \frac{4^2}{12} \right\rangle + \tau(4+1) +4-3 +f(4) \\ &=& 5 +1+2 +4-3 +0 \\ &=& 9. \end{eqnarray*} Thus, there are 9 unigraphical partitions of the integer $8.$ Below we give each of these partitions along with their unique graph realization. \vskip .2in \raisebox{-5mm}{\psset{unit=5mm} \pspicture(-0.2,0)(28.2,3) \rput[b](0,2){$\bullet$} \rput[b](4,2){$\bullet$} %\qline(8,1)(10,1) %\pscircle[linewidth=2pt](2,2){2} \psellipse[linewidth=1pt](2,2)(2,1.5) %\psellipse[linewidth=2pt](2,2)(2,1) \psellipse[linewidth=1pt](2,2.1)(2,0.5) \rput[b](2,-1){\small{$4+4$}} \rput[b](6,2){$\bullet$} \rput[b](8,2){$\bullet$} \rput[b](10,2){$\bullet$} \qline(6,2.2)(10,2.2) \pscircle[linewidth=1pt](7,2.1){1} %\psellipse[linewidth=2pt](2,2)(2,1.5) %\psellipse[linewidth=2pt](2,2)(2,1) %\psellipse[linewidth=2pt](2,2.1)(2,0.5) \rput[b](8,-1){\small{$4+3+1$}} \rput[b](12,2){$\bullet$} \rput[b](14,2){$\bullet$} \rput[b](16,2){$\bullet$} \psellipse[linewidth=1pt](13,2.1)(1,0.5) \psellipse[linewidth=1pt](15,2.1)(1,0.5) %\psellipse[linewidth=2pt](2,2.1)(2,0.5) \rput[b](14,-1){\small{$4+2+2$}} \rput[b](18,2){$\bullet$} \rput[b](20,2){$\bullet$} \rput[b](22,3){$\bullet$} \rput[b](22,1){$\bullet$} \psellipse[linewidth=1pt](19,2.1)(1,0.5) \qline(20,2.2)(22,3.2) \qline(20,2.2)(22,1.2) \rput[b](20,-1){\small{$4+2+1+1$}} \rput[b](24,2){$\bullet$} \rput[b](28,2){$\bullet$} \rput[b](26,3){$\bullet$} \rput[b](26,1){$\bullet$} \rput[b](26,2){$\bullet$} \qline(24,2.2)(28,2.2) \qline(26,1.2)(26,3.2) \rput[b](26,-1){\small{$4+1+1+1+1$}} \endpspicture} \vskip .75in \raisebox{-5mm}{\psset{unit=5mm} \pspicture(-0.2,0)(28.2,3) \rput[b](0,2){$\bullet$} \rput[b](4,2){$\bullet$} \rput[b](2,2){$\bullet$} \qline(0,2.2)(4,2.2) %\pscircle[linewidth=2pt](2,2){2} \psellipse[linewidth=1pt](2,2)(2,1.5) \rput[b](2,-1){\small{$3+3+2$}} \rput[b](6,2){$\bullet$} \rput[b](8,2){$\bullet$} \rput[b](10,3){$\bullet$} \rput[b](10,1){$\bullet$} \rput[b](9,2){$\bullet$} \rput[b](10,2){$\bullet$} \qline(6,2.2)(8,2.2) \qline(8,2.2)(10,3.2) \qline(8,2.2)(10,1.2) \qline(9,2.2)(10,2.2) \rput[b](8,-1){\small{$3+1+1+1+1+1$}} \rput[b](14,2){$\bullet$} \rput[b](16,2){$\bullet$} \rput[b](18,2){$\bullet$} \rput[b](15,1){$\bullet$} \rput[b](17,1){$\bullet$} \rput[b](15,3){$\bullet$} \rput[b](17,3){$\bullet$} \qline(14,2.2)(18,2.2) \qline(15,1.2)(17,1.2) \qline(15,3.2)(17,3.2) \rput[b](16,-1){\small{$2+1+1+1+1+1+1$}} \rput[b](23,1){$\bullet$} \rput[b](23,3){$\bullet$} \rput[b](25,1){$\bullet$} \rput[b](25,3){$\bullet$} \rput[b](26,1){$\bullet$} \rput[b](26,3){$\bullet$} \rput[b](28,1){$\bullet$} \rput[b](28,3){$\bullet$} \qline(23,1.2)(25,1.2) \qline(23,3.2)(25,3.2) \qline(26,1.2)(28,1.2) \qline(26,3.2)(28,3.2) \rput[b](25.5,-1){\small{$1+1+1+1+1+1+1+1$}} \endpspicture} \vskip .5in \end{section} \begin{section}{Proof of the Main Result} \label{sec:proof} \begin{proof} It is easy to check that $d_{\rm uni}(2) = 1$ and $d_{\rm uni}(4)=3.$ Now suppose $m\geq 3.$ Our proof of Theorem~\ref{new_unigraphical} follows by enumerating the degree sequences which fit into each of the five categories in Theorem~\ref{hakimi_char_unigraphical} and then removing those that have been counted multiple times. We begin now with this case--by--case enumeration. %\noindent Case {\it (A)}: In this case, since $d_1+d_2+\dots + d_n = 2m$ and $d_1+d_2+\dots + d_{n-1} = d_n,$ we know that $d_1+d_2+\dots +d_{n-1}$ is a partition of $m$ with no restrictions on the parts. Thus, $p(m)$ enumerates the partitions counted by Case {\it (A)}. %\noindent Case {\it (B)}: We postpone this case briefly. %\noindent Case {\it (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=\dots =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\neq 2.$) Therefore, the number of unigraphical partitions enumerated in this case is $\tau(m+1) - 1.$ %\noindent Case {\it (D)}: Since $d_1+d_2+\dots +d_{n-1} \geq d_n,$ we know that $d_n \leq m.$ With the only additional restriction that $d_1 = d_2 = \dots = d_{n-1} = 1,$ we then see that all partitions of the form $d_n + 1+1+\dots +1$ with $1\leq d_n\leq m$ will be unigraphical. Hence, there are $m$ such partitions counted in this case. %\noindent Case {\it (E)}: In this case, the partitions in question are of the form $d+d+d+1=2m,$ so $2m \equiv 1 \pmod{3},$ and $2m$ is even. Therefore, $2m \equiv 4 \pmod{6}$ which is equivalent to $m\equiv 2\pmod{3}.$ Thus, there is exactly one such partition in this case for each $m\equiv 2 \pmod{3}.$ It is more convenient to enumerate those partitions in {\it (B)} $\setminus$ {\it (A)} than those in {\it (B)} directly. The partitions in {\it (B)} $\setminus$ {\it (A)} satisfy $1\leq d_1 \leq d_2 \leq 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 $\displaystyle{\left\langle \frac{m^2}{12} \right\rangle.}$ See \cite{AND1, HIR1} 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 {\it (A)} $\cap$ {\it (C)}, {\it (A)} $\cap$ {\it (E)}, {\it (B)} $\cap$ {\it (D)}, {\it (B)} $\cap$ {\it (E)}, {\it (C)} $\cap$ {\it (E)}, and {\it (D)} $\cap$ {\it (E)} are all empty. Next, we consider the intersection {\it (A)} $\cap$ {\it (D)}. This intersection consists of the one partition with $d_{m+1} = m$ and $d_1=d_2=\dots = d_{m} = 1.$ In a similar fashion, {\it (C)} $\cap$ {\it (D)} also consists of one partition, namely $d_{m+2} = m-1$ and $d_1=d_2=\dots = d_{m+1} = 1.$ {\it (B)} $\cap$ {\it (C)} consists of those partitions of the form $d+d+(2d-2) = 2m$ which implies $\displaystyle{d=\frac{m+1}{2}.}$ Thus, {\it (B)} $\cap$ {\it (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\geq 3,$ which means we have now covered all possible cases. Combining all of the analysis above, we see that $$ d_{\rm uni}(2m) = p(m) + \left\langle \frac{m^2}{12} \right\rangle +\tau(m+1) +m - 3 + f(m) $$ as defined above. \end{proof} \end{section} \begin{section}{Closing Thoughts} We close by noting that the function $f(m)$ which appears in Theorem~\ref{new_unigraphical} is surprisingly related to Sloane's sequence \seqnum{A083039}. Indeed, $f(m)+2 = A083039(m-2)$ for all $m\geq 3.$ \end{section} \begin{section}{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. \end{section} \begin{thebibliography}{99} \bibitem{AND1} G. E. Andrews, A note on partitions and triangles with integer sides, {\it Amer. Math. Monthly} {\bf 86} (1979), 477. \bibitem{HAK1} S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I, {\it J. Soc. Indust. Appl. Math.} {\bf 10} (1962), 496--506. \bibitem{HAK2} S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. II. Uniqueness, {\it J. Soc. Indust. Appl. Math.} {\bf 11} (1963), 135--147. \bibitem{HIR1} M. D. Hirschhorn, Triangles with integer sides, {\it Math. Mag.} {\bf 76} (2003), 306--308. \bibitem{NJAS} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, \href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/\char'176njas/sequences}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A17, 05C75, 11P81. \noindent \emph{Keywords:} {partition, degree sequence, graph, unigraphical, generating function} \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000005}, \seqnum{A000041}, \seqnum{A001399}, and \seqnum{A083039}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 6 2008; revised version received October 8 2008. Published in {\it Journal of Integer Sequences}, October 18 2008. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}