login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..45.

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: A325667 A067310 A122890 * A331106 A318373 A138497

Adjacent sequences:  A309521 A309522 A309523 * A309525 A309526 A309527

KEYWORD

nonn,tabl,more

AUTHOR

Andrew Howroyd, Sep 06 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 14:46 EDT 2021. Contains 347643 sequences. (Running on oeis4.)