5
$\begingroup$

I'm looking for a characterization of graphs that are prime under the Cartesian product, with prime defined as in this question. Does such a characterization exist, either in general or after restricting to connected bipartite graphs?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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