Is there an algorithm to determine whether a given simple graph $G$ is a product graph, typically, say a cartesian product graph of two smaller simple graphs $G_1, G_2$, such that the two simple graphs have the cartesian product of their vertex sets having the same cardinality of the graph $G$, that is, $V(G_1)\times V(G_2)=V(G)$?

Since every graph could be written as a cartesian product of some graphs(though some might be degenerate), I think it would be possible to determine whether a graph is the product (any graph product) of two simpler graphs in a nice way.

  • 1
    $\begingroup$ I recommend Chapter Five of Algebras, Lattices, Varieties Volume 1 authored by McKenzie, McNulty, and Taylor. Although much of the focus is on algebras having a direct product decomposition (and one can look at the congruences for information on this), some mention is made of relational structures such as graphs. Gerhard "Often Relates To Algebraic Structures" Paseman, 2019.10.22. $\endgroup$ – Gerhard Paseman Oct 22 at 15:00
  • $\begingroup$ @GerhardPaseman could you give some other reference, as the link here has only contents of chapter five. Shall I look in some source dealing with unique factorisation of algebras? $\endgroup$ – vidyarthi Oct 22 at 15:06
  • $\begingroup$ Unique factorization might help, but also search for "direct decomposition" or "direct product decomposition". I recall the chapter talking about Jonsson and Tarski's joint and independent works. If you prefer just to work with graphs however, you might focus on works of graph theorists: some of them have been exposed to universal algebra. Gerhard "Can't Recall Those Names Now" Paseman, 2019.10.22. $\endgroup$ – Gerhard Paseman Oct 22 at 15:23
  • 1
    $\begingroup$ Try to do a bit on your own! Googling "recognising cartesian product of graphs" gives the wikipedia page as first hit, which contains the answer, and the second hit is the paper in Bullet51's answer... $\endgroup$ – verret Oct 22 at 18:28
  • $\begingroup$ @verret actually I never knew that there was a unique factorisation for connected graphs with respect to cartesian products. Didnt read the wikipedia page correctly! So does the set of connected graphs with cartesian product operation as multiplication and disjoint union as addition form a UFD? $\endgroup$ – vidyarthi Oct 22 at 21:31

The best algorithm is linear in the number of edges:see Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics 307 (3-5): 472–483.

An easy-to-understand algorithm can be found here, which is basically keeping a set of edges that necessarily come from the same factor of the product graph. If all edges are necessarily from the same factor, the graph is not a nontrivial product. Otherwise there exists a decomposition.

  • $\begingroup$ thanks! but are there similar algorithms for other products? $\endgroup$ – vidyarthi Oct 22 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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