Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
Please provide the motivation, and explain what you tried. See mathoverflow.net/howtoask –  Boris Bukh Feb 27 '13 at 15:37
    
I'm just working on the graph enumeration and I found this interesting question. Obviously there is no answer in the literature. –  Pop Feb 27 '13 at 16:09
    
No answer in the literature? Where did you search? It is a classic problem. –  Boris Bukh Feb 27 '13 at 16:37
4  
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. –  Theo Johnson-Freyd Feb 27 '13 at 18:39
1  
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. –  Gerry Myerson Feb 27 '13 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.