**
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.
**