length of longest shortest path in the tensor/kronecker square of a graph G?

Question

We have a loopless directed graph $G$.

The tensor square of G is the product of G with itself. (There is an edge from vertex $(u,x)$ to $(v,y)$ only if there is an edge from $u$ to $v$ and from $x$ to $y$ in $G$).

Since there are $n^2$ nodes, it's at most $n^2 - 1$. Is there a better bound?

Answer 1

Here's a lower bound showing that it may be at least $\lceil \frac{n^2}{2}\rceil$.

Let $G$ be the graph with vertices $1, 2, 3, \dots, n$ and edges $1 \to 2 \to 3 \to \dots \to n$ together with $n \to 1$ and $(n-1) \to 1$.

Then in $G$, we can get from vertex $n$ to vertex $j$ in:

• $j$ steps, by going $n \to 1 \to 2 \to \dots \to j$.
• $n+j-1$ or $n+j$ steps, by inserting either the cycle $1 \to 2 \to \dots \to n \to 1$ or the cycle $1 \to 2 \to \dots \to n-1 \to 1$.
• $2n+j-2$, $2n+j-1$, or $2n+j$ steps, by inserting one of these cycles twice.
• In general, for any $k$, we can get from $n$ to $j$ in $kn+j - \{0,1,\dots,k\}$ steps.

This holds for any $j$, including $j=n$.

Let's figure out when $j$'s list of possibilities first overlaps $n$'s list of possibilities: the first length $\ell$ for which we can go from $n$ to $j$ in $\ell$ steps, and also go from $n$ back to $n$ in $\ell$ steps. If we're aiming for the minimum $\ell$, then it doesn't make sense for the $n \to j$ path and $n \to n$ path to both include a cycle of length $n$, or for both to include a cycle of length $n-1$; if we did, skipping that cycle would give us a smaller $\ell$.

So we want to get from $n$ to $n$ inserting only cycles of one kind, while getting from $n$ to $j$ inserting only cycles of the other. There are two situations to consider:

• Going from $n$ to $j$ with $j$ cycles of length $n-1$ inserted takes $j + j(n-1) = jn$ steps, which is the same as going from $n$ to $n$ with $j-1$ cycles of length $n$ inserted.
• Going from $n$ to $n$ with $n-j$ cycles of length $n-1$ inserted takes $n^2-jn+j$ steps, same as going from $n$ to $j$ with $n-j$ cycles of length $n$ inserted.

When $j = \lceil \frac n2\rceil$, both $jn$ and $n^2-jn+j$ are at least $\lceil \frac{n^2}{2}\rceil$.

Therefore in the product $G \times G$, going from $(n,n)$ to $(n,\lceil \frac n2\rceil)$ takes at least $\lceil \frac{n^2}{2}\rceil$ steps.