A326207
Number of non-Hamiltonian labeled simple graphs with n vertices.
Original entry on oeis.org
1, 0, 2, 7, 54, 806, 22690, 1200396, 116759344, 20965139168, 6954959632776, 4363203307789888
Offset: 0
The a(3) = 7 edge sets:
{}
{12}
{13}
{23}
{12,13}
{12,23}
{13,23}
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.
-
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],FindHamiltonianCycle[Graph[Range[n],#]]=={}&]],{n,0,4}] (* Mathematica 8.0+ *)
A126149
Number of connected nonhamiltonian graphs with n nodes.
Original entry on oeis.org
0, 1, 1, 3, 13, 64, 470, 4921, 83997, 2411453, 123544541, 11537642646, 2013389528672
Offset: 1
a(10) = A001349(10) - A003216(10) = number of connected graphs on 10 unlabeled nodes - number of Hamiltonian graphs with 10 nodes = 11716571 - 9305118 = 2411453.
a(11) = A001349(11) - A003216(11) = number of connected graphs on 11 unlabeled nodes - number of Hamiltonian graphs with 11 nodes = 1006700565 - 883156024 = 123544541.
- J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271.
- F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 219.
Cf.
A246446 (number of not-necessarily-connected simple nonhamiltonian graphs on n nodes).
Comments