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

1, 0, 8, 56, 864, 25792

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..5.

Wikipedia, Hamiltonian path

Example

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}

Mathematica

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

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.

Sequence in context: A208944 A209072 A133671 * A154411 A105850 A009089

Adjacent sequences: A326236 A326237 A326238 * A326240 A326241 A326242

Keyword

nonn,more

Author

Gus Wiseman, Jun 16 2019

Status

approved