Palindromes in starlike trees

05/27/2018
by   Amy Glen, et al.
0

In this note, we obtain an upper bound on the maximum number of distinct non-empty palindromes in starlike trees. This bound implies, in particular, that there are at most 4n distinct non-empty palindromes in a starlike tree with three branches each of length n. For such starlike trees labelled with a binary alphabet, we sharpen the upper bound to 4n-1 and conjecture that the actual maximum is 4n-2. It is intriguing that this simple conjecture seems difficult to prove, in contrast to the straightforward proof of the bound.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset