Skip to main content
2 of 2
Changed the name to its family.
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

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.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36