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

[Olivier Gerard]

>
>
> 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
>
>
Yes, this is among other things what I meant, please submit them to the
Oeis.



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

I meant, start from your (now 4) triangles and weigh them by edges:
making two versions: one where each edge is counted for each cycle it is
part of
(just multiply each cycle by its number of edges),
one more difficult but interesting, where each edge is counted only one
time for each graph.

And submit the row sums as well (but they might be in the OEIS)


> 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,...
>
>
Yes this is an important decomposition of A000088.


> 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,...
>
>
Important as well.

Olivier