A326207 Number of non-Hamiltonian labeled simple graphs with n vertices.

1, 0, 2, 7, 54, 806, 22690, 1200396, 116759344, 20965139168, 6954959632776, 4363203307789888

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Comments

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

Examples

			The a(3) = 7 edge sets:
  {}
  {12}
  {13}
  {23}
  {12,13}
  {12,23}
  {13,23}
		

Links

• Wikipedia, Hamiltonian path

Crossrefs

The unlabeled version is A246446.

The directed version is A326220 (with loops) or A326216 (without loops).

Simple graphs with a Hamiltonian cycle are A326208.

Simple graphs without a Hamiltonian path are A326205.

Cf. A003216, A006125, A057864, A283420.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],FindHamiltonianCycle[Graph[Range[n],#]]=={}&]],{n,0,4}] (* Mathematica 8.0+ *)

Formula

A006125(n) = a(n) + A326208(n).

Extensions

a(7)-a(11) from formula by Falk Hüffner, Jun 21 2019