Premium
Packing and covering dense graphs
Author(s) -
Alon Noga,
Caro Yair,
Yuster Raphael
Publication year - 1998
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/(sici)1520-6610(1998)6:6<451::aid-jcd6>3.0.co;2-e
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , disjoint sets , degree (music) , greatest common divisor , discrete mathematics , physics , acoustics
Let d be a positive integer. A graph G is called d ‐divisible if d divides the degree of each vertex of G . G is called nowhere d ‐divisible if no degree of a vertex of G is divisible by d . For a graph H , gcd( H ) denotes the greatest common divisor of the degrees of the vertices of H . The H ‐packing number of G is the maximum number of pairwise edge disjoint copies of H in G . The H ‐covering number of G is the minimum number of copies of H in G whose union covers all edges of G . Our main result is the following: For every fixed graph H with gcd( H ) = d , there exist positive constants ϵ( H ) and N ( H ) such that if G is a graph with at least N ( H ) vertices and has minimum degree at least (1 − ϵ( H ))|G|, then the H ‐packing number of G and the H ‐covering number of G can be computed in polynomial time. Furthermore, if G is either d ‐divisible or nowhere d ‐divisible, then there is a closed formula for the H ‐packing number of G , and the H ‐covering number of G . Further extensions and solutions to related problems are also given. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 451–472, 1998