A283420 - OEIS

%I #23 Feb 16 2025 08:33:42

%S 0,1,2,6,16,65,310,2316,26241,522596,18766354

%N Number of simple (not necessarily connected) untraceable graphs on n nodes.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/UntraceableGraph.html">Untraceable 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="/A283420/a283420_1.png">The a(5) = 16 unlabeled simple graphs not containing a Hamiltonian path</a>.

%F a(n) = A000088(n) - A057864(n).

%Y Cf. A000088 (number of simple graphs on n vertices).

%Y Cf. A057864 (number of simple traceable graphs on n vertices).

%Y Cf. A283421 (number of simple connected untraceable graphs on n vertices).

%Y The labeled case is A326205.

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

%Y Unlabeled simple graphs not containing a Hamiltonian cycle are A246446.

%Y Cf. A003216, A326206, A326217, A326221.

%K nonn,more

%O 1,3

%A _Eric W. Weisstein_, May 14 2017