A326239 Number of non-Hamiltonian labeled n-vertex graphs with loops.

1, 0, 8, 56, 864, 25792

Offset: 0

Author

Gus Wiseman, Jun 16 2019

Keywords

• nonn
• more

Comments

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

Examples

			The a(3) = 56 edge-sets:
  {}  {11}  {11,12}  {11,12,13}
      {12}  {11,13}  {11,12,22}
      {13}  {11,22}  {11,12,23}
      {22}  {11,23}  {11,12,33}
      {23}  {11,33}  {11,13,22}
      {33}  {12,13}  {11,13,23}
            {12,22}  {11,13,33}
            {12,23}  {11,22,23}
            {12,33}  {11,22,33}
            {13,22}  {11,23,33}
            {13,23}  {12,13,22}
            {13,33}  {12,13,33}
            {22,23}  {12,22,23}
            {22,33}  {12,22,33}
            {23,33}  {12,23,33}
                     {13,22,23}
                     {13,22,33}
                     {13,23,33}
                     {22,23,33}
		

Links

• Wikipedia, Hamiltonian path

Crossrefs

The directed case is A326204 (with loops) or A326218 (without loops).

Simple graphs containing a Hamiltonian cycle are A326240.

Simple graphs not containing a Hamiltonian path are A326205.

Cf. A000088, A003216, A006125, A057864, A283420.

Programs

Mathematica

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],OrderedQ]],FindHamiltonianCycle[Graph[Range[n],#]]=={}&]],{n,0,4}]