The On-Line Encyclopedia of Integer Sequences (OEIS)

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A326206 revision #6

A326206

Number of n-vertex labeled simple graphs containing a Hamiltonian path.

10

0, 0, 1, 4, 34, 633, 23368

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

A path is Hamiltonian if it passes through every vertex exactly once.

LINKS

Table of n, a(n) for n=0..6.

Wikipedia, Hamiltonian path

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs.

Gus Wiseman, The a(4) = 34 simple graphs containing a Hamiltonian path

FORMULA

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

MATHEMATICA

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

CROSSREFS

The unlabeled case is A057864.

The directed case is A326214 (with loops) or A326217 (without loops).

Simple graphs without a Hamiltonian path are A326205.

Simple graphs with a Hamiltonian cycle are A326208.

Cf. A003216, A006125, A057864, A283420.

Sequence in context: A333981 A030243 A222789 * * A088077 A358326

Adjacent sequences: A326203 A326204 A326205 * A326207 A326208 A326209

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 14 2019

STATUS

editing