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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .