|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
Cf. A325455 (circumference = longest cycle).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|