[seqfan] Re: Counting cycles in graphs - was Re: A200000

[Andrew Weimholt]

On Tue, Nov 15, 2011 at 12:53 AM, Olivier Gerard
<olivier.gerard at gmail.com> wrote:
> On Tue, Nov 15, 2011 at 06:00, Andrew Weimholt <andrew.weimholt at gmail.com>wrote:
>
>
> Very good one. I didn't think it was not in the OEIS.
>
> Have you calculated the weighted version?
>
> By this, I mean for each n, the sum of all the number of cycles of all the
> graphs with n nodes?
>
> I would very much like to see both in the OEIS (and the associated
> triangles).
>

Hi Olivier,

Is this what you had in mind?...

Total number of cycles on all graphs on n-nodes:

0, 0, 0, 1, 13, 143, 1994, 39688, 1484397, 117971920

Total number of cycles on all connected graphs on n-nodes:

0, 0, 0, 1, 12, 129, 1836, 37534, 1442495, 116445013

I'm not sure how to derive triangles from these.

However, we can consider the following triangles...

T(n,k) = Number of graphs on n nodes with exactly k cycles.

    1,
    1,
    2,
    3, 1,
    6, 3, 0, 1, 0, 0, 0, 1,
    10, 9, 1, 5, 0, 0, 2, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    20, 25, 6, 21, 2, 0, 13, 13, 1, 0, 4, 1, 9, 5, 1, 1, 0, 0, 2, 2,
1, 2, 6, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 3, 1, 1, 0,...

T(n,k) = Number of connected graphs on n nodes with exactly k cycles.

    1,
    1,
    1,
    1, 1,
    2, 2, 0, 1, 0, 0, 0, 1,
    3, 5, 1, 4, 0, 0, 2, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    6, 13, 4, 15, 2, 0, 11, 9, 1, 0, 4, 1, 8, 4, 1, 1, 0, 0, 2, 2, 1,
2, 5, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 2,...

Andrew