tailieunhanh - Báo cáo toán học: "Packing Graphs: The packing problem solved."

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 . 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@ e-mail raphy@ 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 .