Near packings of graphs
type: Item
instance of: scholarly article
title: Near packings of graphs
zbMATH Open document ID: 1266.05127
author: Andrzej Żak
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i2p36
review text: 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).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 6171951
zbMATH Keywords: spanning subgraph
MaRDI profile type: Publication
cites work: Packings of graphs and applications to computational complexity
cites work: Every (p,p-2) graph is contained in its complement
cites work: A near packing of two graphs
cites work: Embedding graphs in their complements
cites work: A note on packing graphs without cycles of length up to five
cites work: Sparse graphs of girth at least five are packable
cites work: Edge disjoint placement of graphs
Recommended article: Near packings of two graphs
Recommended article: A near packing of two graphs
Recommended article: Q4340018
Recommended article: Graph packings
Recommended article: Packings in Dense Regular Graphs
Recommended article: On the packing numbers in graphs
Recommended article: Packings in complete graphs
Recommended article: Packing of graphs - a survey
Recommended article: Q4940073
Recommended article: On perfect packings in dense graphs
description: scientific article; zbMATH DE number 6171951