

A326207


Number of nonHamiltonian labeled simple graphs with n vertices.


5



1, 0, 2, 7, 54, 806, 22690, 1200396, 116759344, 20965139168, 6954959632776, 4363203307789888
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once.


LINKS

Table of n, a(n) for n=0..11.
Wikipedia, Hamiltonian path


FORMULA

A006125(n) = a(n) + A326208(n).


EXAMPLE

The a(3) = 7 edge sets:
{}
{12}
{13}
{23}
{12,13}
{12,23}
{13,23}


MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianCycle[Graph[Range[n], #]]=={}&]], {n, 0, 4}] (* Mathematica 8.0+ *)


CROSSREFS

The unlabeled version is A246446.
The directed version is A326220 (with loops) or A326216 (without loops).
Simple graphs with a Hamiltonian cycle are A326208.
Simple graphs without a Hamiltonian path are A326205.
Cf. A003216, A006125, A057864, A283420.
Sequence in context: A024027 A079410 A283335 * A280221 A227381 A182055
Adjacent sequences: A326204 A326205 A326206 * A326208 A326209 A326210


KEYWORD

nonn,more


AUTHOR

Gus Wiseman, Jun 15 2019


EXTENSIONS

a(7)a(11) from formula by Falk Hüffner, Jun 21 2019


STATUS

approved



