کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776980 | 1413647 | 2017 | 6 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 963-968