Graph Connectivity, Partial Words and a Theorem of Fine and Wilf II
F. Blanchet-Sadri (click to visit homepage)
 Travis Mandel and Gautam Sisodia

Partial words are finite sequences from a finite alphabet that may contain a number of "do not know" symbols or "holes". A variant of Fine and Wilf's theorem states that any partial word with h holes, having periods p, q and length at least the so-denoted L(h,p,q) has also the greatest common divisor of p and q as a period. In this paper, we associate a graph with each p- and q-periodic word, and study two types of vertex connectivity on such a graph: modified degree connectivity and r-set connectivity where r = q mod p. As a result, we give an efficient algorithm for computing L(h,p,q), and give closed formulas in several cases including the h = 3 and h = 4 cases.

Keywords: Combinatorics on words; Partial Words; Fine and Wilf's theorem; Periods; Graph connectivity.

Valid XHTML 1.0! Valid CSS!