# 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?

• Well the maximum of the two diameters is a lower bound for the diameter of the product, and this will often be achieved. Commented Aug 31, 2015 at 8:43

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.