# connected and vertex-transitive prime graphs with respect to Cartesian product

A graph $\Gamma$ is called prime with respect to the Cartesian product if $\Gamma=\Gamma_1\square\Gamma_2$ implies that $\Gamma_1=K_1$ or $\Gamma_2=K_1$, where $\square$ denote the Cartesian product. Is there any classification of connected and vertex-transitive prime graphs with respect to Cartesian product? Is there any information about the automorphism group of such graphs?

• I'm not a graph theorist so excuse me if my question is trivial. Is your notation for Cartesian product (i.e. $\square$) standard in this particular sub-field of mathematics? I think the more commonly used symbol for Cartesian product in most mathematical fields is $\times$. – user82740 Dec 2 '15 at 15:25
• As the book "Handbooks of Product graphs" is a very nice reference for graph products, I used the symbol of this book. However I think that this a common symbol for graph theorists. – majid arezoomand Dec 2 '15 at 16:37
• @AmirBaghban I think one of the reasons $\square$ is used is because the graph $K_2 \square K_2$ ($K_2$ is a graph with just two vertices and one edge between them) is a 4-cycle which is usually drawn in the shape of a square. For direct/categorical product, $\times$ is used because $K_2 \times K_2$ is two disjoint edges, which looks like $\times$ if you draw them crossing. For strong product $K_2 \boxtimes K_2$ is a complete graph on four vertices which can be drawn as $\boxtimes$. There are other products but they usually get some other symbol because all of these are already used up. – David Roberson Dec 4 '15 at 17:17
• @DavidE.Roberson (+1) Nice intuitive explanation! Thanks! – user82740 Dec 4 '15 at 17:20

• This counting argument should work no matter the product. Consider a specific example, for simplicity: graphs of order a power of two. (Which some people expect will dominate the count anyway.) Let $f(n)$ be the number of graphs of order $2^n$. Given a graph product, which takes as input an ordered pair of two graphs and outputs one with order the product of the orders, one has the following upper bound on the number of non-prime graphs of order 2^n: it's at most $f(1)f(n-1)+f(2)f(n-2)+...+f(n-1)f(1)$. – verret Dec 3 '15 at 4:58