Tight Bound for the Number of Distinct Palindromes in a Tree

Abstract

For an undirected tree with n edges labeled by single letters, we consider its substrings, which are labels of the simple paths between pairs of nodes. We prove that there are $O(n^{1.5})$ different palindromic substrings. This solves an open problem of Brlek, Lafrenière and Provençal (DLT 2015), who gave a matching lower-bound construction. Hence, we settle the tight bound of $\mathrm{\Theta }(n^{1.5})$ for the maximum palindromic complexity of trees. For standard strings, i.e., for paths, the palindromic complexity is $n+1$.