Limited packings in graphs

We define a k-limited packing in a graph, which generalizes a 2-packing in a graph, and give several bounds on the size of a k-limited packing. One such bound involves the domination number of the graph, and here we show all trees attaining the bound can be built via a simple sequence of operations. We consider graphs where every maximal 2-limited packing is a maximum 2-limited packing, and characterize their structure in a number of cases.     

The antipode construction for sphere packings

Summary. A construction for sphere packings is introduced that is parallel to the “anticode” construction for codes. This provides a simple way to view Vardy’s recent 20-dimensional sphere packing, and also produces packings in dimensions 22, 44–47 that are denser than any previously known. Oblatum 18-VII-1994 & 7-XII-1994     

The antipode construction for sphere packings

Summary A construction for sphere packings is introduced that is parallel to the anticode construction for codes. This provides a simple way to view Vardy's recent 20-dimensional sphere packing, and also produces packings in dimensions 22, 44–47 that are denser than any previously known.Oblatum 18-VII-1994 & 7-XII-1994     

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

Node packings on cocomparability graphs

We give a compact formulation for the clique inequalities defining the fractional node packing polytope on cocomparability graphs.     

Completing partial packings of bipartite graphs

Given a bipartite graph H and an integer n, let f(n;H) be the smallest integer such that any set of edge disjoint copies of H on n vertices can be extended to an H-design on at most n+f(n;H) vertices. We establish tight bounds for the growth of f(n;H) as n→∞. In particular, we prove the conjecture of Füredi and Lehel (2010) [4] that f(n;H)=o(n). This settles a long-standing open problem.     

Higher dimensional Apollonian packings,revisited

The Apollonian circle and sphere packings are well known objects that have attracted the attention of mathematicians throughout the ages. The historically natural generalization of the procedure for generating the packing breaks down in higher dimensions, as it leads to overlapping hyperspheres. There is, however, an alternative interpretation that allows one to extend the concept to higher dimensions and in a unique way. For relatively small dimensions (2 through at least 8), those packings can be thought of as ample cones for classes of K3 surfaces. We describe the packings in some detail for dimensions 4 (with plenty of pictures), 5, and 6.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

Brambles and independent packings in chordal graphs

An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.     

Density doubling, double-circulants, and new sphere packings

New nonlattice sphere packings in dimensions 20, 22, and 44-47 that are denser than the best previously known sphere packings were recently discovered. We extend these results, showing that the density of many sphere packings in dimensions just below a power of 2 can be doubled using orthogonal binary codes. This produces new dense sphere packings in for and . For the resulting packings are denser than any packing previously known.

     

Perfect packings with complete graphs minus an edge

Let denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥n₀ is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.     

A new bound on the local density of sphere packings

It is shown that a packing of unit spheres in three-dimensional Euclidean space can have density at most 0.773055..., and that a Voronoi polyhedron defined by such a packing must have volume at least 5.41848... These bounds are superior to the best bounds previously published [5] (0.77836 and 5.382, respectively), but are inferior to the tight bounds of 0.7404... and 5.550... claimed by Hsiang [2]. Our bounds are proved by cutting a Voronoi polyhedron into cones, one for each of its faces. A lower bound is established on the volume of each cone as a function of its solid angle. Convexity arguments then show that the sum of all the cone volume bounds is minimized when there are 13 faces each of solid angle 4π/13.     

Remarks on the density of sphere packings in three dimensions

This paper shows how the density of sphere packings of spheres of equal radius may be studied using the Delaunay decomposition. Using this decomposition, a local notion of density for sphere packings in ³ is defined. Conjecturally this approach should yield a bound of 0.740873... on sphere packings in ³, and a small perturbation of this approach should yield the bound of . The face-centered-cubic and hexagonal-close-packings provide local maxima (in a strong sense defined below) to the function which associates to every saturated sphere packing in ³ its density. The local measure of density coincides with the actual density for the face-centered cubic and hexagonal-close-packings.     

Isometries of the unit sphere

It is shown that isometries between the unit spheres of finite dimensional Banach spaces necessarily map antipodal points to antipodal points.     

Large forbidden trade volumes and edge packings of random graphs

Let G be a graph. A G-trade of volume m is a pair (T,T^′), where each of T and T^′ consists of m graphs, pairwise edge-disjoint, isomorphic to G, such that T∩T^′=∅ and the union of the edge sets of the graphs in T is identical to the union of the edge sets of the graphs in T^′. Let X(G) be the set of non-negative integers m such that no G-trade of volume m exists. In this paper we prove that, for G∈G holds asymptotically almost surely, where c=log(4/3)/88.     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

What are all the best sphere packings in low dimensions?

We describe what may beall the best packings of nonoverlapping equal spheres in dimensionsn ≤10, where “best” means both having the highest density and not permitting any local improvement. For example, the best five-dimensional sphere packings are parametrized by the 4-colorings of the one-dimensional integer lattice. We also find what we believe to be the exact numbers of “uniform” packings among these, that is, those in which the automorphism group acts transitively. These assertions depend on certain plausible but as yet unproved postulates. Our work may be regarded as a continuation of László Fejes Tóth's work on solid packings.     

A note on graphs and sphere orders

A partially ordered set P is called a k-sphere order if one can assign to each element a ∈ P a ball B_a in R^k so that a < b iff B_a ? B_b. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3-sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k equals the least k for which P(G) is a k-sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2-dimensional simplicial complex K, there exists a k so that P(K) is a k-sphere order. © 1993 John Wiley & Sons, Inc.