Timeline for graphs which have polynomial bounded number of cycles
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30 at 23:17 | comment | added | Agile_Eagle | @PeterTaylor The second interpretation. I mean it in the sense that for a graph family where there is a graph $G_n$ on $n$ vertices for every $n \in \mathbb{N}$, there is a polynomially $f(n)$ such that the number of cycles in $G_n$ is bounded by $f(n)$. This is true for trees for instance, but false for planar graphs. | |
| Apr 30 at 14:42 | comment | added | Peter Taylor | What does it mean for a graph to "have polynomial bounded number of cycles"? For any given graph the number of cycles is a constant. It makes sense (although in general probably isn't interesting) to pick a specific polynomial $P$ and ask about the class of graphs $(V, E)$ for which the number of cycles is bounded by $P(|V|)$; and it potentially makes sense to ask for which graph classes we can define a polynomial $Q$ such that all graphs $(V, E)$ in that class have number of cycles bounded by $Q(|V|)$, but neither of those appear to be what you're asking about. | |
| Apr 23 at 20:45 | history | asked | Agile_Eagle | CC BY-SA 4.0 |