Packing graphs: The packing problem solved

MaRDI QIDQ1378488zbMATH OpenFDO

Authors Yair Caro, Raphael Yuster

Publication date 12 February 1998

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119247, http://www.emis.de/journals/EJC/Volume_4/Abstracts/v4i1r1.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

decompositionpacking problem

Mathematics Subject Classification ID

Other designs, configurations (05B30) Combinatorial aspects of packing and covering (05B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) General block designs in finite geometry (51E05) Optimal statistical designs (62K05) Statistical block designs (62K10) Applications of design theory to circuits and networks (94C30)

Review text

Summary: For every fixed graph \(H\), we determine the \(H\)-packing number of \(K_n\), for all \(n> n_0(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 \(n_0=n_0(H)\), such that for all \(n> n_0\), \[ P(H,K_n)=\Biggl\lfloor \frac{dn}{2h} \biggl\lfloor \frac{n-1}{d} \biggr\rfloor \Biggr\rfloor, \] unless \(n= 1 \bmod d\) and \(n(n-1)/d= b \bmod (2h/d)\) where \(1 \leq b \leq d\), in which case \[ P(H,K_n)=\Biggl\lfloor \frac{dn}{2h} \biggl\lfloor \frac{n-1}{d} \biggr\rfloor \Biggr\rfloor-1. \] Our main tool in proving this result is the deep decomposition result of Gustavsson.

Recommendations

• scientific article; zbMATH DE number 1229732
• Integer and fractional packings in dense graphs
• On a packing problem of Alon and Yuster
• Solution of two problems of P. Erdős concerning Hamiltonian cycles

Cited in

(25)

• Covering graphs: The covering problem solved
• Packing of graphs and permutations -- a survey
• Packing and decomposition of graphs with trees
• The packing number of the double vertex graph of the path graph
• Orthogonal decomposition and packing of complete graphs
• \(H\)-packing of \(k\)-chromatic graphs
• Intersecting designs
• Clumsy packings of graphs
• On zero-sum spanning trees and zero-sum connectivity
• Asymptotically optimal K_k-packings of dense graphs via fractional K_k-decompositions
• An approximate version of the tree packing conjecture
• Uniform hypergraphs containing no grids
• Combinatorial and computational aspects of graph packing and graph decomposition
• Problems and invariants connected with bicliques and multicliques of graphs
• scientific article; zbMATH DE number 812039 (Why is no real title available?)
• On the packing number of generalized Petersen graphs \(P(n,2)\).
• Leaves for packings with block size four
• Packing copies of Cartesian product of certain classes of paths and cycles into power graphs
• Block allocation of a sequential resource
• Packing cliques in 3‐uniform hypergraphs
• Graph and hypergraph packing
• Completing partial packings of bipartite graphs
• Generalising Fisher's inequality to coverings and packings
• Triangle-free triple systems
• Planar packing of trees and spider trees

This page was built for publication: Packing graphs: The packing problem solved

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378488)