EUVIMEDEUVIMED entdecken
Crossref

On the sizes of generalized cactus graphs

Licheng Zhang, Yuanqiu Huang

Discrete Applied Mathematics · 2024-05 · 348 · 184-191

DOI: 10.1016/j.dam.2024.01.043 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2024-05. Verfasst von Licheng Zhang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 18 Literaturangaben. Gefördert von: Hunan Provincial Natural Science Foundation, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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\ge 1$. It is well known that every cactus with $n$ vertices has at most $\lfloor\frac{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\le k\le 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\ge 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 ~(\ge 1)$-cactus graphs with $n$ vertices has at most $n+k-1$ edges, and the bound is tight if $n \ge k + 2$. But, for $n

Förderung

  • Hunan Provincial Natural Science Foundation
  • National Natural Science Foundation of China

Zitieren

APA

Zhang, L., & Huang, Y. (2024). On the sizes of generalized cactus graphs. Discrete Applied Mathematics, 348, 184-191. https://doi.org/10.1016/j.dam.2024.01.043

Vancouver

Zhang L, Huang Y. On the sizes of generalized cactus graphs. Discrete Applied Mathematics. 2024;348:184-191. doi:10.1016/j.dam.2024.01.043

BibTeX
@article{Zhang2024,
  author = {Zhang, Licheng and Huang, Yuanqiu},
  title = {On the sizes of generalized cactus graphs},
  journal = {Discrete Applied Mathematics},
  year = {2024},
  volume = {348},
  pages = {184--191},
  doi = {10.1016/j.dam.2024.01.043}
}
Kostenlos starten →