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?
$\begingroup$
$\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$– Brendan McKayCommented 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$– domotorpCommented 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$– user83660Commented Dec 4, 2015 at 18:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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)$.
answered Apr 17, 2015 at 1:00
$\begingroup$
$\endgroup$
3
For planar graphs there are recent (exponential) bounds, as in Buchin et al, 2007.
answered Apr 16, 2015 at 20:11
-
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$– domotorpCommented 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$ Commented 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$ Commented Apr 17, 2015 at 0:26