4
$\begingroup$

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle.

The following is well known about the upper border for cactus graph class.

Theorem 1. The maximum number of edges in a simple $n$-vertex cactus $G$ is $\left\lfloor{\frac{3(n-1)}{2}}\right\rfloor$.The bound is achieved by a set of $ \lfloor (n − 1)/2 \rfloor $ triangles sharing a single vertex, plus one extra edge to a leaf if $n$ is even.

The theorem can be found on page 160 of West's book. The proof content can also be easily referred to the answers in its appendix.

  • West D B. Introduction to graph theory[M]. Upper Saddle River: Prentice hall, 2001.

I want to think about a broader graph class than the cactus class. It is a connected graph in which every edge belongs to at most $k$ simple cycle. I do not know whether a definition of this graph class exists. We'll temporarily call it the $k$-cactus graph. So we have a similar problem with the upper bound of the edge of the $k$-cactus graph.

Problem 1. What is the maximum number of edges in a simple $n$-vertex $k$-cactus graph?

In particular, $k=2$ is what we care about most.

Appendix: The four proofs of Theorem 1.

enter image description here

enter image description here

$\endgroup$
5
  • $\begingroup$ Hello! Do you have any results about these 2-cactus graphs in which every edge belongs to at most 2 simple cycles? $\endgroup$ Commented May 6, 2023 at 7:23
  • $\begingroup$ @BjørnKjos-Hanssen Thank you very much for your interest in this question. I did prove a result privately last year. I'll have time to add this proof later. $\endgroup$
    – L.C. Zhang
    Commented May 6, 2023 at 12:44
  • 1
    $\begingroup$ @BjørnKjos-Hanssen Due to the answer being too long, we have written an article, which should soon be uploaded to arXiv (if not, and you're interested, I will send it to your email address, hoping I can find your correct email). There are more questions worth further exploration in it, and perhaps there is a possibility for collaboration. $\endgroup$
    – L.C. Zhang
    Commented Jun 28, 2023 at 13:36
  • $\begingroup$ Sounds good! $\phantom{...}$ $\endgroup$ Commented Jun 29, 2023 at 3:45
  • 1
    $\begingroup$ @BjørnKjos-Hanssen See arxiv.org/abs/2307.08039. We have just posted it on arXiv. $\endgroup$
    – L.C. Zhang
    Commented Jul 18, 2023 at 3:12

1 Answer 1

1
$\begingroup$

For $k=2,3,4$, we solved this question. But for large $k$, we may need more deep tools.

More details can be seen in L.C.Zhang, Y.Q. Huang, On the sizes of generalized cactus graphs, Discrete Applied Mathematics, 348 (2024) 184-191 doi.org/10.1016/j.dam.2024.01.043

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.