The problem of computing periods in * words*, or finite sequences of symbols from a finite alphabet,
has important applications in several areas including data compression, string searching and pattern
matching algorithms. The notion of *period* of a word is central in combinatorics on words. There are many
fundamental results on periods of words. Among them is the well known and basic periodicity result of Fine and Wilf which
intuitively determines how far two periodic events have to match in order to guarantee a common period. More precisely,
any word with length at least *p+q-*gcd(*p,q*) having periods *p* and *q* has also period the greatest common divisor of *p*
and *q*, gcd(*p,q*). Moreover, the bound *p+q-*gcd(*p,q*) is optimal since counterexamples can be provided for words of smaller length.

*Partial words*, or finite sequences that may contain a number of "do not know" symbols or *holes*, appear in natural ways
in several areas of current interest such as molecular biology, data communication, DNA computing, etc. Any long enough partial word with *h* holes
and having periods *p, q* has also period gcd(*p,q*). In this paper, we give closed formulas for the optimal bounds *L(h,p,q)* in
the case where *p*=2 and also in the case where *q* is large. In addition, we give upper bounds when *q* is small and
*h*=3,4,5 or 6. No closed formulas for *L(h,p,q)* were known except for the cases where *h*=0,1 or 2. Our proofs are based on
connectivity in graphs associated with partial words.

*Keywords*: Words; partial words; Fine and Wilf's Theorem; periods; graph connectivity