On the sizes of generalized cactus graphs
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.
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}
}
EUVIMED