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](https://en.wikipedia.org/wiki/Tensor_product_of_graphs).)


In terms of $d\_1, d\_2$ what is the minimum and maximum value that $\text{diam}(G\_1\times G\_2)$ can take? 



Maximum and minimum diameter of categorical graph product
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. 


