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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ 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$. $\endgroup$– user82740Commented Dec 2, 2015 at 15:25
-
1$\begingroup$ 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. $\endgroup$– majid arezoomandCommented Dec 2, 2015 at 16:37
-
4$\begingroup$ @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. $\endgroup$– David RobersonCommented Dec 4, 2015 at 17:17
-
$\begingroup$ @DavidE.Roberson (+1) Nice intuitive explanation! Thanks! $\endgroup$– user82740Commented Dec 4, 2015 at 17:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
There almost certainly isn't a meaningful classification of vertex-transitive prime graphs. In fact, it's quite likely that almost all vertex-transitive graphs are prime.
-
$\begingroup$ Dear Gabriel, thank you for your answer. Is this your conjecture that almost all vertex-transitive graphs are prime or there exists any reference? $\endgroup$ Commented Dec 3, 2015 at 2:29
-
$\begingroup$ How do you think about vertex-transitive prime graphs with respect to direct product, strong product and lexicographic product? $\endgroup$ Commented Dec 3, 2015 at 2:31
-
$\begingroup$ In the unpublished paper " vertex-transitive graphs and their arc-types" written by Conder, Pisanski and Zitnik, infinitely many vertex-transitive prime graphs are introduced. $\endgroup$ Commented Dec 3, 2015 at 2:55
-
$\begingroup$ Exhibiting infinitely many vertex-transitive prime graphs is trivial. Take the cycles of prime order, for example. As for my "almost all" statement, I would think about it a bit more before I would call it a conjecture, but I'm almost certain it's true. There is an easy upper bound on the number of non-prime graph of a given order in terms of the number of smaller graphs. So, intuitively at least, if the number of graphs grows fast enough and somewhat smoothly (I'll stay vague on purpose here), then the upper bound will be much smaller than the number of graphs. $\endgroup$– verretCommented Dec 3, 2015 at 4:53
-
$\begingroup$ 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)$. $\endgroup$– verretCommented Dec 3, 2015 at 4:58
$\begingroup$
$\endgroup$
1
It's all in Hammock, Imrich and Klavzar "Handbook of Product Graphs". The rough summary is that everything works nicely, and you do not need transitivity. The automorphism group will be the direct product of wreath products.
answered Dec 2, 2015 at 14:36
-
$\begingroup$ Dear Prof. Godsil, thank you for your answer. In the book" Handbook of Product graphs" in Theorem 6.6, it is proved that every connected graph has a unique prime factorization up to isomorphisms and the order of factors. Also as you noted, the automorphism group is the direct product of the wreath products on the sets of pairwise isomorphic factors. If a graph is prime, then I think that this result can not help us to get any information about its automorphism group. $\endgroup$ Commented Dec 2, 2015 at 16:33