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

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

Offset: 1

Author

Eric W. Weisstein, May 14 2017

Keywords

• nonn
• more

Links

• Eric Weisstein's World of Mathematics, Untraceable Graph
• Wikipedia, Hamiltonian path
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
• Gus Wiseman, The a(5) = 16 unlabeled simple graphs not containing a Hamiltonian path.

Crossrefs

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

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

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

The labeled case is A326205.

The directed case is A326224 (with loops).

Unlabeled simple graphs not containing a Hamiltonian cycle are A246446.

Cf. A003216, A326206, A326217, A326221.

Formula

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