Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Packing Graphs: The packing problem solved | Packing Graphs The packing problem solved Yair Caro and Raphael Yuster 1 Department of Mathematics University of Haifa-ORANIM Tivon 36006 Israel. AMS Subject Classification 05B05 05B40 primary 05B30 51E05 94C30 62K05 62K10 secondary . Submitted November 28 1996 Accepted December 2 1996 Dedicated to the memory of Paul Erdos Abstract For every fixed graph H we determine the H-packing number of Kn for all n n0 H . We prove that if h is the number of edges of H and gcd H d is the greatest common divisor of the degrees of H then there exists no n0 H such that for all n n0 PHKn Ib JJ. unless n 1 mod d and n n 1 d b mod 2h d where 1 b d in which case P H.K. I d n b -r JJ 1 Our main tool in proving this result is the deep decomposition result of Gustavsson. 1 Introduction All graphs considered here are finite undirected and simple. For the standard graph-theoretic terminology the reader is referred to Bo . Let H be a graph without isolated vertices. An H-packing of a graph G is a set L G1 . Gs of edge-disjoint subgraphs of G where each subgraph e-mail zeac603@uvm.haifa.ac.il e-mail raphy@math.tau.ac.il 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 4 1997 R1 2 is isomorphic to H. The H-packing number of G denoted by P H G is the maximum cardinality of an H-packing of G. An H-covering of a graph G is a set L G1 . Gs of subgraphs of G where each subgraph is isomorphic to H where every edge of G appears in at least one member of L. The H-covering number of G denoted by C H G is the minimum cardinality of an H-covering of G. G has an H-decomposition if it has an H-packing which is also an H-covering. The H-packing and H-covering problems are in general NP-Complete as shown by Dor and Tarsi DoTa . In case G Kn the H-covering and H-packing problems have attracted much attention in the last forty years and numerous papers were written on these subjects cf. Br95 Ha MiMu CoDi StKaMu for various surveys . Special cases of these problems gained particular interest. 1. P Kk Kn which has .
