2
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Well the maximum of the two diameters is a lower bound for the diameter of the product, and this will often be achieved. $\endgroup$ – Gordon Royle Aug 31 '15 at 8:43
3
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.