login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A321593 Smallest number of vertices supporting a graph with exactly n Hamiltonian paths. 1
4, 1, 4, 3, 4, 5, 4, 5, 6, 7, 5, 6, 4, 7, 5, 7, 6, 6, 5, 7, 6, 7, 6, 7, 5, 7, 6, 8, 6, 7, 6, 7, 6, 7, 6, 7, 5, 7, 6, 7, 6, 8, 7, 7, 7, 6, 7, 7, 6, 8, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 5, 7, 6, 7, 8, 7, 7, 7, 7, 7, 6, 7, 6, 8, 7, 7, 6, 8, 7, 7, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 6, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 7 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

The reverse of a path is counted as the same path. a(n) is well-defined as the cycle graph C_n has n paths.

a(n) >= A249905(n) - 1, since the number of Hamiltonian paths in G is the same as the number of Hamiltonian cycles in H, where H is G with a new vertex connected to all vertices in G.

LINKS

Jeremy Tan, Table of n, a(n) for n = 0..2412

Erich Friedman, Math Magic (September 2012).

EXAMPLE

a(12) = 4 since K_4 has 12 Hamiltonian paths, and no graph on less than 4 vertices has 12 Hamiltonian paths.

CROSSREFS

The corresponding sequence for Hamiltonian cycles is A249905.

Sequence in context: A016686 A060037 A229705 * A173259 A267633 A021711

Adjacent sequences:  A321590 A321591 A321592 * A321594 A321595 A321596

KEYWORD

nonn,hard

AUTHOR

Jeremy Tan, Nov 14 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 6 04:15 EDT 2020. Contains 334859 sequences. (Running on oeis4.)