Almost-perfect packings and Tuza's conjecture in the random geometric graph
2026-06-08 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study how to pack triangles in random geometric graphs, where points are placed randomly and edges connect points that are close. They prove that a known conjecture by Tuza about covering triangles with edges holds true for many such graphs. They also explore how to cover almost all edges of these graphs with copies of a fixed smaller graph, showing that almost perfect coverings exist for a large group of these smaller graphs. Some limitations of these packings are also discussed.
triangle packing numberTuza's conjecturerandom geometric graphedge-disjoint trianglesgraph packingcovering edgesgraph theorycombinatoricsperfect packingfixed graph
Authors
Patrick Bennett, Ryan Cushman, Andrzej Dudek, Xavier Pérez-Giménez
Abstract
The triangle packing number $ν(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2ν(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random geometric graph for a large range of densities. We also study the problem of covering almost all edges of the random geometric graph with edge-disjoint copies of some fixed graph $F$. In particular, we show the existence of almost-perfect packings for an infinite family of $F$, and state some negative results as well.