A357360 - OEIS

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

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

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

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.

KEYWORD

nonn,more

AUTHOR

STATUS

approved