Palindromes in starlike trees

Glen, A., Simpson, J. and Smyth, W.F. (2019) Palindromes in starlike trees. Australasian Journal of Combinatorics, 73 (1). pp. 242-246.

Abstract

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 4 n 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 4 n − 1 and conjecture that the actual maximum is 4 n − 2. It is intriguing that this simple conjecture seems difficult to prove, in contrast to the proof of the bound.

Publication Type:	Journal Article
Murdoch Affiliation:	School of Engineering and Information Technology
Publisher:	Combinatorial Mathematics Society of Australasia
Copyright:	© 2019 The author(s).
URI:	http://researchrepository.murdoch.edu.au/id/eprint/42923

Item Control Page

Downloads