Cartesian Product of Graphs Algorithm

Question

I am not quite sure what I am asking but I am having trouble finding the proper context in Google. I wanted to take the Cartesian Product of a certain graph using Sagemath; however, I think either I am doing it wrong or perhaps it is taking too long to calculate. I am not sure. What is the fastest algorithm for taking the G$\square $G of a graph? Is it possible in polynomial time? I think the best way I can ask this is to perhaps direct me to some articles to read? Not sure. Here is my code:

> M = Matrix([(0,1,1,0,0,0,0,0),(1,0,0,1,0,0,0,0), (1,0,0,0,1,1,1,0), (0,1,0,0,1,1,1,1),(0,0,1,1,0,0,0,1),(0,0,1,1,0,0,0,1), (0,0,1,1,0,0,0,1),(0,0,0,1,1,1,1,0)])
G = Graph(M); G
H = G.cartesian_product(G)

Answer 1

I'm not sure what the issue is. I get

%time H = G.cartesian_product(G)
CPU times: user 724 µs, sys: 186 µs, total: 910 µs
Wall time: 885 µs

when trying this on Sage cell server. Even for $K_{32}$ I only get 87.4 microseconds with timeit.

Here is the (brief) documentation on this function. Note also the documentation for identifying Cartesian products, which is of course a very different question.