2026/06/04 by Yuanqiu Huang, Licheng Zhang
Mathematics · #math.CO
A cactus is a graph in which every edge lies on at most one cycle. In 2024, Zhang and Huang generalized this concept to the k-cactus, defined as a graph in which every edge lies on at most k cycles. It is known that any cactus on n vertices has at most \lfloor(3)/(2)(n-1)\rfloor edges. However, the upper bound on the size of k-cacti was known only for k≤ 4. In this note we consider general k. We prove that every n-vertex k-cactus has O ((log k)/(√(loglog k)) n) edges for all sufficiently large k, and a construction shows this is optimal up to a factor of √(loglog k).