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

Author

Pontus von Brömssen, Sep 25 2022

Keywords

• nonn
• more

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.

Examples

			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.

Formula

a(n) <= A099155(n).