  Two vectors $x,y$ in $\mathbb{Z}_g^n$ are $ qualitatively$ $ independent$ if
for all pairs $(a,b)\in \mathbb{Z}_g\times \mathbb{Z}_g$, there exists $i\in
\{1,2,\ldots,n\}$ such that $(x_i,y_i)=(a,b)$. A covering array on a graph $G$,
denoted by $CA(n,G,g)$, is a $|V(G)|\times n$ array on $\mathbb{Z}_g$ with the
property that any two rows which correspond to adjacent vertices in $G$ are
qualitatively independent. The number of columns in such array is called its
$size$. Given a graph $G$, a covering array on $G$ with minimum size is called
$optimal$. Our primary concern in this paper is with constructions that make
optimal covering arrays on large graphs those are obtained from product of
smaller graphs. We consider four most extensively studied graph products in
literature and give upper and lower bounds on the the size of covering arrays
on graph products. We find families of graphs for which the size of covering
array on the Cartesian product achieves the lower bound. Finally, we present a
polynomial time approximation algorithm with approximation ratio
$\log(\frac{V}{2^{k-1}})$ for constructing covering array on graph $G=(V,E)$
with $k>1$ prime factors with respect to the Cartesian product.
