Near packings of graphs (Q1953525): Difference between revisions

Summary: A packing of a graph \(G\) is a set \(\{G_1,G_2\}\) such that \(G_1\cong G\), \(G_2\cong G\), and \(G_1\) and \(G_2\) are edge disjoint subgraphs of \(K_n\). Let \(\mathcal{F}\) be a family of graphs. A near packing admitting \(\mathcal{F}\) of a graph \(G\) is a generalization of a packing. In a near packing admitting \(\mathcal{F}\), the two copies of \(G\) may overlap so the subgraph defined by the edges common to both copies is a member of \(\mathcal{F}\). In the paper we study three families of graphs (1) \(\mathcal{E}_k\) -- the family of all graphs with at most \(k\) edges, (2) \(\mathcal{D}_k\) -- the family of all graphs with maximum degree at most \(k\), and (3) \(\mathcal{C}_k\) -- the family of all graphs that do not contain a subgraph of connectivity greater than or equal to \(k+1\). By \(m(n,\mathcal{F})\) we denote the maximum number \(m\) such that each graph of order \(n\) and size less than or equal to \(m\) has a near-packing admitting \(\mathcal{F}\). It is well known that \(m(n,\mathcal{C}_0)=m(n,\mathcal{D}_0)=m(n,\mathcal{E}_0)=n-2\) because a near packing admitting \(\mathcal{C}_0, \mathcal{D}_0\) or \(\mathcal{E}_0\) is just a packing. We prove some generalization of this result, namely we prove that \( m(n,\mathcal{C}_k)\approx (k+1)n\), \(m(n,\mathcal{D}_1)\approx \frac{3}{2}n\), \(m(n,\mathcal{D}_2)\approx 2n\). We also present bounds on \(m(n,\mathcal{E}_k)\). Finally, we prove that each graph of girth at least five has a near packing admitting \(\mathcal{C}_1\) (i.e., a near packing admitting the family of the acyclic graphs).