I need to compute the number $f(n,k)$ of graphs on $n$ vertives having a cycle of length $k$.
We can consider the graphs are labelled or not.
11
-
2$\begingroup$ Please provide the motivation, and explain what you tried. See mathoverflow.net/howtoask $\endgroup$– Boris BukhCommented Feb 27, 2013 at 15:37
-
$\begingroup$ I'm just working on the graph enumeration and I found this interesting question. Obviously there is no answer in the literature. $\endgroup$– PopCommented Feb 27, 2013 at 16:09
-
$\begingroup$ No answer in the literature? Where did you search? It is a classic problem. $\endgroup$– Boris BukhCommented Feb 27, 2013 at 16:37
-
4$\begingroup$ I second Boris Bukh's comment: please provide more details, motivation, and so on. Most mathematicians don't like thinking about unmotivated and uncontextualized questions. Note that because certain graphs have extra symmetries, often exact formulas are much simpler or much more complicated (to the point of being unavailable) depending on whether you work with labeled or unlabeled graphs. It can also happen that what you care about are certain asymptotics, rather than exact formulas. So all of these concerns might be included in your question, and will guide answers. $\endgroup$– Theo Johnson-FreydCommented Feb 27, 2013 at 18:39
-
2$\begingroup$ oeis.org/A006785 counts the number of triangle-free graphs on $n$ vertices, and oeis.org/A000088 counts the number of graphs on $n$ vertices, so the difference gives you $f(n,3)$. The links and references may or may not lead to formulas. $\endgroup$– Gerry MyersonCommented Feb 27, 2013 at 23:21
|
Show 6 more comments