# Recognition of a graph as a product of its quotients

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.

• 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. – Gerhard Paseman Oct 22 at 15:00
• @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? – vidyarthi Oct 22 at 15:06
• 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. – Gerhard Paseman Oct 22 at 15:23
• 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... – verret Oct 22 at 18:28
• @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? – vidyarthi Oct 22 at 21:31