|
|
A326207
|
|
Number of non-Hamiltonian labeled simple graphs with n vertices.
|
|
5
|
|
|
1, 0, 2, 7, 54, 806, 22690, 1200396, 116759344, 20965139168, 6954959632776, 4363203307789888
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(3) = 7 edge sets:
{}
{12}
{13}
{23}
{12,13}
{12,23}
{13,23}
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianCycle[Graph[Range[n], #]]=={}&]], {n, 0, 4}] (* Mathematica 8.0+ *)
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|