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$
  • $\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$ – Brendan McKay Apr 17 '15 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 '15 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 '15 at 18:34
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$
  • 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 '15 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 '15 at 20:17
  • $\begingroup$ @Igor: How does an example provide a lower bound? It can only provide a lower bound on the maximum. $\endgroup$ – Brendan McKay Apr 17 '15 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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