Maximum and minimum diameter of categorical graph product Let $G_i$ be connected finite simple undirected graphs with diameter $d_i$ for $i=1,2$. Assume that $G_1\times G_2$ is connected. (Here $G_1\times G_2$ denotes the categorical product.)
In terms of $d_1, d_2$ what is the minimum and maximum value that $\text{diam}(G_1\times G_2)$ can take? 
 A: As Prof. Royle said, there is such upper bound which happen in many times. But, there is a good paper which this diameter exactly determined and maybe it is useful for you.
The paper is: "On the diameter of the Kronecker product graph" by "Fu-Tao Hu" and "Jun-Ming Xu".
you can find this paper in the Arxiv.
Also, maybe this view also good. We know that the distinct eigenvalues of a graph depend to its diameter. Actually, the graph $G_1$ and $G_2$ has at least $d_1+1$ and $d_2+1$ distinct eigenvalues, respectively. Now, suppose that the distinct eigenvalues of $G_1$ and $G_2$ are $\lambda_i$ and $\mu_j$, respectively. Therefore, the eigenvalues of categorical product of these two graphs are $\{\lambda_i\mu_j\}$. So, the question can rephrase as follows:
We have two set $A$ and $B$ which have the size $a$ and $b$, respectively. What is the maximum and minimum size of the set $A.B=\{rs: r\in A,s\in B\}$? As I know, we have some good upper and lower bound for this question, which I think I saw some of them in Prof. Tao's WordPress blog. 
