

A326239


Number of nonHamiltonian labeled nvertex graphs with loops.


4




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 edgesets:
{} {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



