|
| |
|
|
A326239
|
|
Number of non-Hamiltonian labeled n-vertex 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 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
|
| |
|
|
