I'm looking for a characterization of graphs that are prime under the Cartesian product, with prime defined as in [this question](https://mathoverflow.net/questions/225094/connected-and-vertex-transitive-prime-graphs-with-respect-to-cartesian-product). Does such a characterization exist, either in general or after restricting to connected bipartite graphs?



Which graphs are prime under the Cartesian product?
For connected graphs, they are the graphs in which every two edges are connected by a sequence of pairwise relations using one or both of the following two types of relation:


* Edge $xy$ and $uv$ are related if $d(x,u)+d(y,v)\ne d(x,v)+d(y,u)$
* Edge $xy$ and $yv$ are related if $y$ is the only common neighbor of $x$ and $v$.


See Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics 307 (3-5): 472–483. In Theorem 3.1, they state more strongly that the transitive closure of the union of the two types of relation above is an equivalence relation whose equivalence classes give the prime factorization of the graph. They credit the theorem to T. Feder, Product graph representations, J. Graph Theory 16 (1992) 467–488.


If you need a characterization for disconnected graphs, it's going to get messier (for one thing, factorization is not unique) and involve graph isomorphism.


