کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5776980 1413647 2017 6 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
Near packings of two graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 5, May 2017, Pages 963-968
نویسندگان
, ,