{"id":"arxiv/2606.06298","url":"https://arxiv.org/abs/2606.06298","tags":["math.CO"],"score":0,"title":"On the maximum number of edges of k-cacti","domain":"math.CO","source":"arxiv","authors":["Yuanqiu Huang","Licheng Zhang"],"reviews":0,"subject":"math.CO","summary":"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\\frac{3}{2}(n-1)\\rfloor$ edges. However, the upper bound on the size of $k$-cacti was known only for $k\\le 4$. In this note we consider general $k$. We prove that every $n$-vertex $k$-cactus has $O\\!\\left(\\frac{\\log k}{\\sqrt{\\log\\log k}}\\,n\\right)$ edges for all sufficiently large $k$, and a construction shows this is optimal up…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-04","reactions":{}}