|
%I #7 Sep 03 2019 09:53:13
%S 1,0,8,56,864,25792
%N Number of non-Hamiltonian labeled n-vertex graphs with loops.
%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>
%e The a(3) = 56 edge-sets:
%e {} {11} {11,12} {11,12,13}
%e {12} {11,13} {11,12,22}
%e {13} {11,22} {11,12,23}
%e {22} {11,23} {11,12,33}
%e {23} {11,33} {11,13,22}
%e {33} {12,13} {11,13,23}
%e {12,22} {11,13,33}
%e {12,23} {11,22,23}
%e {12,33} {11,22,33}
%e {13,22} {11,23,33}
%e {13,23} {12,13,22}
%e {13,33} {12,13,33}
%e {22,23} {12,22,23}
%e {22,33} {12,22,33}
%e {23,33} {12,23,33}
%e {13,22,23}
%e {13,22,33}
%e {13,23,33}
%e {22,23,33}
%t Table[Length[Select[Subsets[Select[Tuples[Range[n],2],OrderedQ]],FindHamiltonianCycle[Graph[Range[n],#]]=={}&]],{n,0,4}]
%Y The directed case is A326204 (with loops) or A326218 (without loops).
%Y Simple graphs containing a Hamiltonian cycle are A326240.
%Y Simple graphs not containing a Hamiltonian path are A326205.
%Y Cf. A000088, A003216, A006125, A057864, A283420.
%K nonn,more
%O 0,3
%A _Gus Wiseman_, Jun 16 2019
|
