login
A309524
Triangle read by rows: T(n,k) is the number of simple connected graphs on n nodes with longest path having k nodes, (1 <= k <= n).
2
1, 0, 1, 0, 0, 2, 0, 0, 1, 5, 0, 0, 1, 2, 18, 0, 0, 1, 3, 17, 91, 0, 0, 1, 3, 29, 86, 734, 0, 0, 1, 4, 42, 176, 864, 10030, 0, 0, 1, 4, 64, 309, 2032, 10243, 248427
OFFSET
1,6
COMMENTS
Paths here are subgraphs that are isomorphic to a path graph and are measured by the number of vertices they contain rather than the number of edges. No vertex can appear more than once.
Paths with three vertices exist in all connected graphs with at least three vertices. For n > 3, the star graph is the only graph in which longer paths are not possible.
LINKS
Eric Weisstein's World of Mathematics, Longest Path
Eric Weisstein's World of Mathematics, Traceable Graph
EXAMPLE
Triangle begins:
1;
0, 1;
0, 0, 2;
0, 0, 1, 5;
0, 0, 1, 2, 18;
0, 0, 1, 3, 17, 91;
0, 0, 1, 3, 29, 86, 734;
0, 0, 1, 4, 42, 176, 864, 10030;
0, 0, 1, 4, 64, 309, 2032, 10243, 248427;
...
CROSSREFS
Row sums are A001349.
Right diagonal is A057864.
Cf. A325455 (circumference = longest cycle).
Cf. A307457.
Sequence in context: A067310 A369321 A122890 * A331106 A318373 A138497
KEYWORD
nonn,tabl,more
AUTHOR
Andrew Howroyd, Sep 06 2019
STATUS
approved