Contact graphs of unit sphere packings revisited (Q1956324)

The vertices of the contact graph of a finite packing of unit balls in Euclidean \(3\)-space correspond to the single balls of the packing. Two vertices are connected by an edge if the respective balls touch each other. The following are shown: A contact graph with \(n\) vertices has less than \(6n-0.926n^{\frac{2}{3}}\) edges. This improves a former bound from [\textit{K. Bezdek}, Discrete Comput. Geom. 48, No. 2, 298--309 (2012; Zbl 1259.52013)]. A contact graph with \(n\) vertices contains at most \(\frac{25}{3}n\) triangles and at most \(\frac{11}{4}n\) complete subgraphs with \(4\) vertices. The authors point out that recent work of T. C. Hales allows to reduce the last two bounds to \(8n\) and \(\frac{5}{2}n\), respectively. Similar results are obtained for contact graphs of lattice packings of unit balls.