\title{Packing Graphs:\\
The packing problem solved}

\author{Yair Caro \thanks{e-mail: zeac603@uvm.haifa.ac.il}\\
and\\
Raphael Yuster \thanks{e-mail: raphy@math.tau.ac.il}\\
Department of Mathematics\\
University of Haifa-ORANIM, Tivon 36006, Israel.\\
{\bf AMS Subject Classification:} 05B05,05B40 (primary),\\
05B30,51E05,94C30,62K05,62K10 (secondary).\\
\\
Submitted: November 28, 1996; Accepted: December 2, 1996
}

\date{} %Prevent the date from being printed
\documentstyle [11pt]{article}

% SIDE MARGINS:
\hsize=6in
\vsize=9in
\oddsidemargin 0pt %Left margin on odd-numbered pages.
\evensidemargin 0pt %Left margin on even-numbered pages.
\marginparwidth 40pt %Width of marginal notes.
\marginparsep 10pt %Horizontal space between outer margin and note.

% VERTICAL SPACING:
\topmargin 0pt %Distance from top of page to running head.
\headsep 10pt %Space between running head and text.

% DIMENSION OF TEXT:
\textheight 8.4in %Height of text excluding running head and foot.
\textwidth 6.5in %Width of text line.

\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{conj}[theo]{Conjecture}
\renewcommand{\baselinestretch}{1.3}
\newcommand{\ignore}[1]{}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4 (1997), \#R1\hfill}
\thispagestyle{empty}
\begin{document}
\maketitle
\setcounter{page}{1}
\begin{center}
Dedicated to the memory of Paul Erd\H os
\end{center}
\begin{abstract}

\noindent
For every fixed graph $H$, we determine the $H$-packing number of
$K_n$, for all $n > n_0(H)$. We prove that
if $h$ is the number of edges of $H$, and $gcd(H)=d$ is the greatest common
divisor of the degrees of $H$, then there  exists
$n_0=n_0(H)$, such that for all $n > n_0$,
$$
P(H,K_n)=\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor,
$$
unless $n = 1 \bmod d$ and $n(n-1)/d = b \bmod (2h/d)$ where
$1 \leq b \leq d$, in which case
$$
P(H,K_n)=\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor - 1.
$$
Our main tool in proving this result is the deep decomposition result
of Gustavsson.
\end{abstract}

\section{Introduction}
All graphs considered here are finite, undirected and simple. For the
standard graph-theoretic terminology the reader is referred to \cite{Bo}.
Let $H$
be a graph without isolated vertices. An {\em $H$-packing} of a graph
$G$ is a set $L=\{G_1, \ldots, G_s\}$ of edge-disjoint subgraphs of $G$,
where each subgraph is isomorphic to $H$. The {\em $H$-packing number} of
$G$, denoted by $P(H,G)$, is the maximum cardinality of an $H$-packing of
$G$.  An {\em $H$-covering} of a graph
$G$ is a set $L=\{G_1, \ldots, G_s\}$ of subgraphs of $G$,
where each subgraph is isomorphic to $H$, where every edge of $G$ appears
in at least one member of $L$. The {\em $H$-covering number} of
$G$, denoted by $C(H,G)$, is the minimum cardinality of an $H$-covering of
$G$. $G$ has an {\em $H$-decomposition} if it has an $H$-packing which is
also an $H$-covering.
The $H$-packing and $H$-covering problems are, in general, NP-Complete
as shown by Dor and Tarsi \cite{DoTa}. In case $G=K_n$, the $H$-covering
and $H$-packing problems have attracted much attention in the last forty
years, and numerous papers were written on these subjects (cf.
\cite{Br95,Ha,MiMu,CoDi,StKaMu} for various surveys). Special cases
of these problems gained particular interest. 
\begin{enumerate}
\item
$P(K_k,K_n)$ which has been linked to the various Johnson-Schonheim bounds 
in Coding Theory \cite{BiEt,BrShSlSm,Sc,Jo}. It is known that $P(K_k,K_n)$ is
the maximum size of the binary codes of word-length $n$, constant weight
$k$, and distance $2k-2$ or $2k-3$.
Despite of much effort only the cases $k=3$ \cite{Sc} and $k=4$ \cite{Br79}
are solved. The case $k=5$ is still open \cite{MuYi}.
\item
$P(C_k,K_n)$ which is the cycle-system packing problem, solved completely
only for $k=3$, $k=4$ \cite{ScBi} and $k=5$ \cite{RoZn}. 
\item
The packing-covering conjecture for trees saying that 
$P(T,K_n) = \lfloor {n \choose 2}/h \rfloor$ and
$C(T,K_n) = \lceil {n \choose 2}/h \rceil$
($h$ is the number of edges of $T$) provided $n$ is sufficiently large.  
This conjecture has been proved for all trees on at most 7 vertices
\cite{Ro83,Ro93}.
\end{enumerate}

\noindent
A central result concerning $H$-decompositions of $K_n$ is the theorem
of Wilson \cite{Wi} stating that for sufficiently large $n$, $K_n$ has an
$H$-decomposition if and
only if $e(H) \; | \; {n \choose 2}$ and $gcd(H) \; | \; n-1$ where 
$gcd(H)$ is the greatest common divisor of the degrees of $H$. Clearly,
if the conditions in Wilson's Theorem hold, then the packing and 
covering numbers are known. 

In this paper we solve all of the conjectures above, for large $n$,
as special consequences of a much more general result.
In fact, for every $H$, we determine $P(H,K_n)$, for all $n \geq n_0(H)$.
\begin{theo}
\label{t11}
Let $H$ be a graph with $h$ edges, and let gcd(H)=d. Then there  exists
$n_0=n_0(H)$, such that for all $n > n_0$,
$$
P(H,K_n)=\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor,
$$
unless $n = 1 \bmod d$ and $n(n-1)/d = b \bmod (2h/d)$ where
$1 \leq b \leq d$, in which case
$$
P(H,K_n)=\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor - 1.
$$
\end{theo}

\section{Proof of the main result}
As mentioned in the abstract, our main tool is the following result
of Gustavsson \cite{Gu}:
\begin{lemma}[Gustavsson's Theorem \cite{Gu}]
\label{l21}
Let $H$ be a graph with $h$ edges. There exists
$N=N(H)$, and $\epsilon = \epsilon(H) > 0$, such that for all
$n > N$, If $G$ is a graph on $n$ vertices and $m$ edges, with
$\delta(G) \geq n(1 - \epsilon)$, $gcd(H) \; | \; gcd(G)$, and $h \; | \; m$,
then $G$ has an $H$-decomposition. $\Box$
\end{lemma}
It is worth mentioning that $N(H)$ in Gustavsson's Theorem is a rather
huge constant; in fact, it is a highly exponential function of $h$.

A sequence of $n$ positive integers $d_1 \geq d_2 \geq \ldots \geq d_n$
is called {\em graphic} if there exists an $n$-vertex graph whose degree
sequence is $\{d_1, \ldots, d_n\}$.
We shall need the following theorem of Erd\H os and Gallai \cite{ErGa},
which gives a necessary and sufficient condition for a sequence to be
graphic.
\begin{lemma}[Erd\H os and Gallai \cite{ErGa}]
\label{l22}
The sequence $d_1 \geq d_2 \geq \ldots \geq d_n$ of positive integers is
graphic if and only if its sum is even and for every $t=1,\ldots,n$
\begin{equation}
\label{e1}
\sum_{i=1}^t d_i \leq t(t-1) + \sum_{i=t+1}^n \min\{t,d_i\}.
\end{equation} $\Box$
\end{lemma}

\noindent
{\bf Proof of Theorem \ref{t11}:}\,
Given $H$, we choose $n_0=n_0(H)=\max \{N(H), \frac{2h}{\epsilon(H)}, 8h\}$,
where $N(H)$ and $\epsilon(H)$ are as in Lemma \ref{l21}. Now let
$n > n_0$. Let $n-1 = a \bmod d$, where $0 \leq a \leq d-1$. Let
$n(n-1-a)/d = b \bmod (2h/d)$, where $0 \leq b \leq 2h/d - 1$. Note that
since $d=gcd(H)$ and $2h$ is the sum of the degrees of $H$, $2h/d$ must
be an integer. Also note that $(n-1-a)/d$ is an integer, and so $b$ is
well-defined. We shall use the obvious fact that $h \geq d(d+1)/2$,
since $\delta(H) \geq d$. This means that
$$
n  > n_0 \geq 8h > 4d^2 > (a+d)^2.
$$
Another useful fact is that $bd+na$ is even since if $d$ is even then
$a$ and $n$ have different parity, and if $d$ is odd then $2h/d$
is even and so if $b$ is odd then $a$ and $n$ are both odd, and if
$b$ is even then either $n$ is even or $a$ is even.
In the first part of the proof we shall give a lower bound
for $P(H,K_n)$, and in the second part we shall give an upper bound
for $P(H,K_n)$, and notice that the lower and upper bounds coincide.

\noindent
{\bf Proving a lower bound for $P(H,K_n)$:}\,
We shall first assume that $a \neq 0$.
Our first goal is to show the existence of an $n$-vertex graph
which has $b$ vertices with degree $d+a$, and $n-b$ vertices
with degree $a$. For this purpose we shall use Lemma \ref{l22},
with $d_i=a+d$ for $i=1,\ldots,b$ and $d_i=a$ for $i=b+1,\ldots,n$.
Notice first that the sum of the sequence is $bd+na$ and this number
is even as mentioned above.
Let $1 \leq t \leq a+d$. In this case, (\ref{e1}) holds since
$$
\sum_{i=1}^t d_i \leq t(a+d) = t(t-1) + t(a+d-t+1) \leq
t(t-1) + (a+d)(a+d-1) =
$$
$$
t(t-1) + (a+d)^2 - (a+d) < t(t-1) + n - (a+d) \leq
t(t-1) + (n-t) \leq t(t-1) + \sum_{i=t+1}^n \min\{t,d_i\}.
$$
For $a+d \leq t \leq n$ we shall prove that (\ref{e1}) holds by induction
on $t$, where the base case $t=a+d$ was proved above. If $t > a+d$ we
use the induction hypothesis to derive that
$$
\sum_{i=1}^t d_i = d_t + \sum_{i=1}^{t-1} d_i \leq
d_t + (t-1)(t-2) + \sum_{i=t}^n \min\{t,d_i\} =
$$
$$
d_t + \min\{t,d_t\} -2(t-1) + t(t-1) + \sum_{i=t+1}^n \min\{t,d_i\}
$$
$$
\leq (a+d) + (a+d) -2(a+d) + t(t-1) + \sum_{i=t+1}^n \min\{t,d_i\} =
t(t-1) + \sum_{i=t+1}^n \min\{t,d_i\}.
$$
Thus, there exists a graph $G^*$ having $b$ vertices with degree $d+a$ and
$n-b$ vertices with degree $a$. Consider $G=K_n \setminus G^*$.
Clearly, $d \; | \; gcd(G)$, and $G$ has $m$ edges where
$$
m = {n \choose 2} - \frac{bd+na}{2} =
\frac{d}{2} ( \frac{n(n-1-a)}{d}-b)) = 0 \bmod h.
$$
Also note that $\delta(G) \geq n-1-a-d = n(1-\frac{1+a+d}{n}) \geq
n(1-\epsilon(H))$,
since $n > n_0 \geq \frac{2h}{\epsilon(H)}$. Thus, $G$ satisfies the
conditions of Lemma \ref{l21}, and therefore $G$ has an
$H$-decomposition. This means that
$$
P(H,K_n) \geq P(H,G) = \frac{m}{h} = \frac{d}{2h} ( \frac{n(n-1-a)}{d}-b)) =
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor.
$$

\noindent
We now deal with the case $a=0$. If $b = 0$ then $K_n$ has an
$H$-decomposition according to Wilson's Theorem \cite{Wi}, (or
according to Lemma \ref{l21}), so, trivially,
$$
P(H,K_n) = \frac{{n \choose 2}}{h} =
\frac{dn}{2h} \frac{n-1}{d} = 
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor.
$$
If $b > d$ we may delete from $K_n$ a subgraph $G^*$ on $b$ vertices which
is $d$ regular (this is doable since $bd+na=bd$ is even). As in the
case where $a \neq 0$, the remaining graph $G = K_n \setminus G^*$ satisfies
the conditions of Lemma \ref{l21} and therefore
$$
P(H,K_n) \geq P(H,G) = \frac{{n \choose 2} - \frac{bd}{2}}{h} =
\lfloor \frac{{n \choose 2}}{h} \rfloor = 
\lfloor \frac{dn}{2h} \frac{n-1}{d} \rfloor =
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor.
$$
Finally, if $1 \leq b \leq d$ then we can delete from $K_n$ a subgraph $G^*$
on $b+\frac{2h}{d}$ vertices which is $d$ regular. Note that this can be
done since $h \geq d(d+1)/2$ which implies $d \leq \frac{2h}{d} <
\frac{2h}{d}+b$. Also, if $d$ is odd then $b$ and $\frac{2h}{d}$ are both
even, so $b+\frac{2h}{d}$ is even. Once again, the remaining graph 
$G = K_n \setminus G^*$ satisfies the conditions of Lemma \ref{l21} and
we get
$$
P(H,K_n) \geq P(H,G) = \frac{{n \choose 2} - \frac{(b+(2h/d))d}{2}}{h} =
\frac{{n \choose 2} - \frac{bd}{2}}{h} - 1 =
\lfloor \frac{{n \choose 2}}{h} \rfloor - 1 = 
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor - 1.
$$

\noindent
{\bf Proving an upper bound for $P(H,K_n)$:}\,
Let $L$ be an arbitrary $H$-packing of $K_n$. Let $s$ denote the cardinality
of $L$. Let $G$ denote the edge-union of all the members of $L$.
$G$ contains $sh$ edges. Thus $G^* = K_n \setminus G$ contains
${n \choose 2} - sh$ edges. The degree of every vertex in $G$ is $0 \bmod d$
and so the degree of every vertex in $G^*$ is $a \bmod d$. Therefore, the
number of edges in $G^*$ satisfies 
$$
{n \choose 2} - sh = \frac{an+cd}{2}
$$
for some non-negative integer $c$. In particular, 
${n \choose 2} = \frac{an+cd}{2} \bmod h$. This, in turn, implies that
$n(n-1-a)/d = c \bmod (2h/d)$. Thus, we must have $c \geq b$.
Therefore,
$$
s = \frac{{n \choose 2} -\frac{an+cd}{2}}{h} \leq  
\frac{{n \choose 2} -\frac{an+bd}{2}}{h} = 
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor.
$$
Since $L$ was an arbitrary $H$-packing, we have
$$
P(H,K_n) \leq \lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor.
$$
The only remaining case is $a=0$ and $1 \leq b \leq d$.
In this case, we cannot have $c=b$. This is because every non-isolated
vertex of $G^*$ has degree at least $d$, and therefore there are at least
$d(d+1)/2$ edges in $G^*$, i.e $cd/2 \geq d(d+1)/2$, which implies
$c \geq d+1$, but $b \leq d$. We must, therefore have $c \geq b +  2h/d$.
Therefore,
$$
s = \frac{{n \choose 2} -\frac{an+cd}{2}}{h} \leq  
\frac{{n \choose 2} -\frac{an+(b+2h/d)d}{2}}{h} = 
\lfloor \frac{dn}{2h} \lfloor \frac{n-1}{d} \rfloor \rfloor - 1.
$$ $\Box$

\section{Concluding remarks}
\begin{enumerate}
\item
Theorem \ref{t11}, applied to $H=K_k$ yields, for $n \geq n_0(k)$, that
$$
P(K_k,K_n) = \lfloor \frac{n}{k} \lfloor \frac{n-1}{k-1} \rfloor \rfloor,
$$
unless $k-1 \; | \; n-1$ and $n(n-1)/(k-1) \bmod k$ is less than $k$ and
greater than 0, in which case the above formula should be reduced by 1.
This solves, in particular, the related problem in Coding Theory mentioned
in the introduction.
\item
Theorem \ref{t11}, applied to $H=C_k$ yields, for $n \geq n_0(k)$, that
$$
P(C_k,K_n) = \lfloor \frac{n}{k} \lfloor \frac{n-1}{2} \rfloor \rfloor
$$
unless $n$ is odd and ${n \choose 2} = 1,2 \bmod k$.
\item
If $n \geq n_0(H)$ and
$gcd(H)=1$, then $P(H,K_n) = \lfloor \frac{{n \choose 2}}{e(H)} \rfloor$.
Note that by first deleting from $K_n$ any set of $b < e(H)$ edges where
$b = {n \choose 2} \bmod e(H)$, the remaining graph satisfies the
conditions in Gustavsson's Theorem, and since the set of deleted edges
may be chosen as a subgraph of $H$ we have $C(H,K_n) =   
\lceil \frac{{n \choose 2}}{e(H)} \rceil$, solving, in particular, the
packing-covering conjecture for trees.
\end{enumerate}

Our approach allows us to solve the covering problem as well. This is
done in a forthcoming paper \cite{CaYu}.

\section{Acknowledgment}
The authors wish to thank N. Alon, T. Etzion, R. Mullin, J. Schonheim and 
Y. Roditty for
useful discussions, helpful information, and sending important references.

\begin{thebibliography}{99}

\bibitem{BiEt} S. Bitan and T. Etzion,
{\em The last packing number of quadruples and cyclic SQS},
Design, Codes and Cryptography 3 (1993), 283-313.

\bibitem{Br79} A.E. Brouwer,
{\em Optimal packing of $K_4$'s into a $K_n$},
J. Combin. Theory, Ser. A 26 (1979), 278-297. 

\bibitem{Br95} A.E. Brouwer,
{\em Block Designs},
in: Chapter 14 in "Handbook of Combinatorics",
R. Graham, M. Gr\"otschel and L. Lov\'asz Eds. Elsevier, 1995.

\bibitem{BrShSlSm} A. Brouwer, J. Shearer, N. Sloane and W. Smith,
{\em A new table of constant weight codes},
IEEE Trans. Inform. Theory 36 (1990), 1334-1380.

\bibitem{Bo} B. Bollob\'as,
{\em Extremal Graph Theory}, Academic Press, 1978.

\bibitem{CaYu} Y. Caro and R. Yuster,
{\em Covering graphs: The covering problem solved}, submitted.

\bibitem{CoDi} C.J. Colbourn and J.H. Dinitz,
{\em CRC Handbook of Combinatorial Design},
CRC press 1996.

\bibitem{DoTa} D. Dor and M. Tarsi,
{\em Graph decomposition is NPC - A complete proof of Holyer's 
conjecture}, Proc. 20th ACM STOC, ACM Press (1992), 252-263.

\bibitem{ErGa} P. Erd\H os and T. Gallai,
{\em Graphs with prescribed degrees of vertices (Hungarian)},
Math. Lapok 11 (1960), 264-274.

\bibitem{Gu} T. Gustavsson,
{\em Decompositions of large graphs and digraphs with high minimum
degree},
Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991.

\bibitem{Ha} H. Hanani,
{\em Balanced incomplete block designs and related designs},
Discrete Math. 11 (1975), 255-369.

\bibitem{Jo} S.M. Johnson,
{\em A new upper bound for error-correcting codes},
IEEE Trans. Inform. Theory 8 (1962), 203-207.

\bibitem{MiMu} W.H. Mills and R.C. Mullin,
{\em Coverings and packings}, in: Contemporary Design Theory: A collection
of Surveys, 371-399, edited by J. H. Dinitz and D. R. Stinson. Wiley, 1992.

\bibitem{MuYi} R.C. Mullin and J. Yin,
{\em On packing of pairs by quintuples $v = 3,9,17 (\bmod 20)$},
Ars Combinatoria 35 (1993), 161-171.

\bibitem{Ro83} Y. Roditty,
{\em Packing and covering of the complete graph with a graph $G$ of four
vertices or less}, J. Combin. Theory, Ser. A 34 (1983), 231-243. 

\bibitem{Ro93} Y. Roditty,
{\em Packing and covering of the complete graph IV, the trees of order 7},
Ars Combinatoria 35 (1993), 33-64. 

\bibitem{RoZn} A. Rosa and S. Znam,
{\em Packing pentagons into complete graphs: how clumsy can you get},
Discrete Math. 128 (1994), 305-316
\bibitem{Sc} J. Schonheim,
{\em On maximal systems of $k$-tuples},
Studia Sci. Math. Hungar. (1966), 363-368.

\bibitem{ScBi} J. Schonheim and A. Bialostocki,
{\em Packing and covering of the complete graph with 4-cycles},
Canadian Math. Bull. 18 (1975), 703-708.

\bibitem{StKaMu} R.G. Stanton, J.G. Kalbfleisch and R.C. Mullin,
{\em Covering and packing designs},
Proc. $2^{nd}$ Chapel Hill Conf. on Combinatorial Mathematics and its
applications. Univ. North Carolina, Chapel Hill (1970) 428-450.

\bibitem{Wi} R. M. Wilson,
{\em Decomposition of complete graphs into subgraphs isomorphic to a given
graph}, Congressus Numerantium XV (1975), 647-659.

\end{thebibliography}
\end{document}