Low expansion packings and embeddings of hypercubes into star graphs

Let G(κ) and H(n) be respectively a κ-dimensional and an n-dimensional graph. Packing is a technique by which p_κ many copies of each G(κ), κ_min⩽κ⩽κ_max, are embedded into H(n). Packings can use H(n) efficiently by assigning independent tasks to the embedded copies of G(κ), and are a useful foundation, from which node allocation and task migration strategies can be built. Copies of G(κ), packed into H(n) with dilation d_base, can be combined to produce a variable-dilation embedding of G(κ+l) into H(n). Such an embedding has dilation d _i along dimension i of G(κ+l), where d_i=d _base for i⩽κ, and d_i>d_base for κ<i⩽κ+l. The average dilation of the embedding is d_avr=1/(κ+l)Σ_i=1^κ+ld _i, and can often be made close to d_base. This paper focuses on the problem of packing hypercubes Q(κ) into a star graph S(n) with load 1 and dilation 3. Our results include: 1) fixed-sized packings of Q(κ) into S(n), 2) multiple-sized packings of Q(κ) into S(n), and 3) variable-dilation embeddings of Q(κ+l) into S(n). Our variable-dilation embeddings and multiple-sized packings provide flexibility to support tasks with a wide range of node allocation requirements. The expansion of our multiple-sized packings is optimal (i.e., 1), which solves the problem of growing expansion found in single embeddings of hypercubes into star graphs. Moreover, for n⩽10, the average dilation of our variable-dilation embeddings lies between 3 and 4.25