2
$\begingroup$

How does the graph class defined as those graphs which have polynomial (or quasi polynomial) bounded number of cycles look? (in number of vertices)

I suspect it will rather non-interesting as something very close to a tree (maybe bounded treewidth) but a reference would be nice.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Apr 30 at 14:42
  • $\begingroup$ @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. $\endgroup$
    – Agile_Eagle
    Commented Apr 30 at 23:17

0

Reset to default

You must log in to answer this question.