7
$\begingroup$

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is $m-n$, then after a while it starts to grow exponentially with $m$. What is known about this function?

$\endgroup$
3
  • $\begingroup$ If the rate of growth accelerates as more edges are added, it can't literally become exponential until we are only $O(n\log n)$ edges short of a complete graph. Is that inconsistent with what you know? $\endgroup$ Apr 17, 2015 at 0:56
  • $\begingroup$ @Brendan: To be honest, I did not spend too much time thinking about this, it was just obvious that the end becomes exponential. I am more interested in the beginning, like the function in Tony's answer, except that I want the minimum number of cycles. $\endgroup$
    – domotorp
    Apr 17, 2015 at 5:58
  • $\begingroup$ I know what the domain and the range is but it is so had some time but I can get it done.(((: $\endgroup$
    – user83660
    Dec 4, 2015 at 18:34

2 Answers 2

5
$\begingroup$

To supplement Igor's answer, here is some more information on the maximum number of cycles a graph on $n$ vertices with $m$ edges can have. I apologize that this does not answer your question. Entringer and Slater considered this problem in their paper On the Maximum Number of Cycles in a Graph.

Let $G$ be a simple connected graph with $m$ edges and $n$ vertices. It is useful to re-parametrize by letting $d=m-n+1$, and defining $\psi(d)$ to be the maximum number of cycles of a graph with $m-n+1=d$. They observed that since $d$ is the dimension of the cycle space of $G$, $\psi(d) \leq 2^d-1$. On the other hand, they showed that the Möbius ladders imply that $\psi(d) \geq 2^{d-1}+d^2-3d+3$. Using exhaustive computer search they also determined $\psi(d)$ for all $d \leq 8$, and conjectured that the lower bound is essentially the right answer for $\psi(d)$.

$\endgroup$
2
$\begingroup$

For planar graphs there are recent (exponential) bounds, as in Buchin et al, 2007.

$\endgroup$
3
  • 1
    $\begingroup$ This paper is also about the most number of cycles a graph might have. It is also of interest, but here the number of edges is not given. $\endgroup$
    – domotorp
    Apr 16, 2015 at 20:15
  • 1
    $\begingroup$ @domotorp true, but for planar graphs there is an implied upper bound (linear in the number of vertices), and the explicit examples in the paper provide lower bounds. $\endgroup$
    – Igor Rivin
    Apr 16, 2015 at 20:17
  • $\begingroup$ @Igor: How does an example provide a lower bound? It can only provide a lower bound on the maximum. $\endgroup$ Apr 17, 2015 at 0:26

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.