login
Number of simple traceable graphs on n nodes.
21

%I #23 Sep 07 2019 11:55:15

%S 1,1,2,5,18,91,734,10030,248427,11482572,1000231510

%N Number of simple traceable graphs on n nodes.

%C Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).

%H F. Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version f0eaa32.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TraceableGraph.html">Traceable Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>

%H Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.

%H Gus Wiseman, <a href="/A057864/a057864.png">Non-isomorphic representatives of the a(5) = 18 unlabeled simple graphs containing a Hamiltonian path</a>.

%F A000088(n) = a(n) + A283420(n). - _Gus Wiseman_, Jun 17 2019

%Y Main diagonal of A309524.

%Y The labeled case is A326206.

%Y The directed case is A326221 (with loops).

%Y Unlabeled simple graphs not containing a Hamiltonian path are A283420.

%Y Unlabeled simple graphs containing a Hamiltonian cycle are A003216.

%Y Cf. A000088, A006125, A246446, A283420, A326205, A326217.

%K nonn,more

%O 1,3

%A _Eric W. Weisstein_

%E a(8) and a(9) from _Eric W. Weisstein_, Jun 04 2004

%E a(10) from _Eric W. Weisstein_, May 27 2009

%E a(11) added using tinygraph by _Falk Hüffner_, Jan 19 2016