Timeline for Number of graphs with a cycle
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 19, 2016 at 21:42 | comment | added | D. Ror. | @BarryCipra After checking a few more terms, it appears to me that whatever discrepancy you saw among those three sequences has been corrected. | |
| Mar 28, 2013 at 1:44 | comment | added | Rodrigo A. Pérez | Can some moderator add a lot of reputation points to Theo? This is a very clear justification for our paying attention to how questions are posed... | |
| Mar 14, 2013 at 0:17 | comment | added | Barry Cipra | @Gerry, oeis.org/A128236 counts the number of (unlabeled) graphs of girth 3 -- meaning, I take it, they have a shortest path of length 3 (i.e., a triangle) -- which suggests it should match up as the difference of the two sequences you cited. But except for the first few values (up to $n=6$), it doesn't. Am I missing something? | |
| Feb 28, 2013 at 0:33 | comment | added | Brendan McKay | Is there one particular cycle of length $k$ that is distinguished, or do you just want to find how many graphs have at least one cycle of length $k$? | |
| Feb 27, 2013 at 23:21 | comment | added | Gerry Myerson | 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. | |
| Feb 27, 2013 at 18:39 | comment | added | Theo Johnson-Freyd | 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. | |
| Feb 27, 2013 at 16:51 | comment | added | Pop | I did a new search on google and I still have not found the solution. | |
| Feb 27, 2013 at 16:45 | comment | added | Pop | I look at the books on enumeration. If you have a reference for this problem, I am very interested. | |
| Feb 27, 2013 at 16:37 | comment | added | Boris Bukh | No answer in the literature? Where did you search? It is a classic problem. | |
| Feb 27, 2013 at 16:20 | history | edited | Pop | CC BY-SA 3.0 |
edited title
|
| Feb 27, 2013 at 16:09 | comment | added | Pop | I'm just working on the graph enumeration and I found this interesting question. Obviously there is no answer in the literature. | |
| Feb 27, 2013 at 15:37 | comment | added | Boris Bukh | Please provide the motivation, and explain what you tried. See mathoverflow.net/howtoask | |
| Feb 27, 2013 at 14:44 | history | asked | Pop | CC BY-SA 3.0 |