2021/08/05 by Mahalingam, Kalpana, Pandoh, Palak
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2108.02729
We investigate the scattered palindromic subwords in a finite word. We start by characterizing the words with the least number of scattered palindromic subwords. Then, we give an upper bound for the total number of palindromic subwords in a word of length n in terms of Fibonacci number Fn by proving that at most Fn new scattered palindromic subwords can be created on the concatenation of a letter to a word of length n-1. We propose a conjecture on the maximum number of scattered palindromic subwords in a word of length n with q distinct letters. We support the conjecture by showing its validity for words where q≥ (n)/(2).