login
Number of non-Hamiltonian labeled simple graphs with n vertices.
5

%I #10 Jun 21 2019 07:57:57

%S 1,0,2,7,54,806,22690,1200396,116759344,20965139168,6954959632776,

%T 4363203307789888

%N Number of non-Hamiltonian labeled simple graphs with n vertices.

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

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

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

%e The a(3) = 7 edge sets:

%e {}

%e {12}

%e {13}

%e {23}

%e {12,13}

%e {12,23}

%e {13,23}

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

%Y The unlabeled version is A246446.

%Y The directed version is A326220 (with loops) or A326216 (without loops).

%Y Simple graphs with a Hamiltonian cycle are A326208.

%Y Simple graphs without a Hamiltonian path are A326205.

%Y Cf. A003216, A006125, A057864, A283420.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jun 15 2019

%E a(7)-a(11) from formula by _Falk Hüffner_, Jun 21 2019