A326239 - OEIS

%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