2023/07/16 by Licheng Zhang, Yuanqiu Huang, Zhang, Licheng +1
Computer Science · #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2307.08039
openalex publication_date 2023/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A cactus is a connected graph in which each edge is contained in at most one cycle. We generalize the concept of cactus graphs, i.e., a k-cactus is a connected graph in which each edge is contained in at most k cycles where k≥ 1. It is well known that every cactus with n vertices has at most \lfloor(3)/(2)(n-1) \rfloor edges. Inspired by it, we attempt to establish analogous upper bounds for general k-cactus graphs. In this paper, we first characterize k-cactus graphs for 2≤ k≤ 4 based on the block decompositions. Subsequently, we give tight upper bounds on their sizes. Moreover, the corresponding extremal graphs are also characterized. However, the case of k≥ 5 remains open. For the case of 2-connectedness, the range of k is expanded to all positive integers in our research. We prove that every 2-connected k ~(≥ 1)-cactus graphs with n vertices has at most n+k-1 edges, and the bound is tight if n ≥ k + 2. But, for n < k+1, determining best bounds remains a mystery except for some small values of k.