Near packings of two graphs

A packing of two graph G1 and G2 is a set {H1,H2} such that H1≅G1, H2≅G2, and H1 and H2 are edge disjoint subgraphs of Kn. Let F be a family of graphs. A F-near-packing of G1 and G2 is a generalization of a packing. In a F-near-packing, H1 and H2 may overlap so the subgraph defined by the edges common to both of them is a member of F. In the paper we study three families of graphs (1) Ek -the family of all graphs with at most k edges, (2) Dk -the family of all graphs with maximum degree at most k, and (3) Kk -the family of all graphs having the clique number at most k. By m(n,F) we denote the smallest number m such that there are graphs G1 and G2 both of order n with |E(G1)|+|E(G2)|=m which do not have a F-near-packing. It is well known that m(n,E0)=m(n,D0)=m(n,K1)=3(n−1)2+1 because a E0, D0 or K1-near-packing is just a packing. In this paper we prove that m(n,E1)=m(n,D1)=2n−1 and, for sufficiently large n, m(n,D2)=5(n−1)2+1. We also obtain distinct bounds on m(n,Ek) for k≥2, m(n,D3), and m(n,Kk) for k≥2, under conditions imposed on n and k.