A357360 Maximum length of an induced path (or chordless path or snake path) between two antipodal nodes of the n-dimensional hypercube.

0, 1, 2, 3, 4, 11, 24

Offset

0,3

Comments

The length is defined as the number of edges along the path, so the number of nodes of the longest path is a(n)+1.

Links

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

Formula

a(n) <= A099155(n).

Example

For n <= 4, the only induced paths between two antipodal nodes are the shortest paths, so a(n) = n.
For n = 5, a longest induced path is 00000 - 10000 - 11000 - 11100 - 01100 - 01110 - 00110 - 00111 - 00011 - 10011 - 11011 - 11111, so a(5) = 11.

Crossrefs

Cf. A099155 (the ends of the path does not have to be antipodal), A357234 (paths between opposite corners of a square grid).

Main diagonal of A357499.

Sequence in context: A139763 A037396 A037432 * A301877 A369438 A221172

Adjacent sequences: A357357 A357358 A357359 * A357361 A357362 A357363

Keyword

nonn,more

Author

Pontus von Brömssen, Sep 25 2022

Status

approved