Near packings of graphs
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).
- Near packings of two graphs
- A near packing of two graphs
- scientific article; zbMATH DE number 1022391
- Graph packings
- Packings in Dense Regular Graphs
- On the packing numbers in graphs
- Packings in complete graphs
- Packing of graphs - a survey
- scientific article; zbMATH DE number 1409232
- On perfect packings in dense graphs
- A near packing of two graphs
- A note on packing graphs without cycles of length up to five
- Edge disjoint placement of graphs
- Embedding graphs in their complements
- Every (p,p-2) graph is contained in its complement
- Packings of graphs and applications to computational complexity
- Sparse graphs of girth at least five are packable
- Packing closed trails into dense graphs.
- Packing without some pieces
- Packing degenerate graphs greedily
- A near packing of two graphs
- Clumsy packings of graphs
- Graphs with unique maximum packing of closed neighborhoods
- Packing minor closed families of graphs
- A note on careful packing of a graph
- Near packings of two graphs
- Packing in regular graphs
- On asymptotic packing of convex geometric and ordered graphs
- Near packings with restriction on degrees in graphs
- Enumeration of packed graphs
This page was built for publication: Near packings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1953525)
