Skip to main content
added 3 characters in body
Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 125

I am mainly interested in the leastsmallest 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?

I am mainly interested in the least 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?

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?

Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 125

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the least 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?