4
$\begingroup$

Given graphs $X$ and $Y$, their modular product, which I will denote by $X \diamond Y$, has vertex set $V(X) \times V(Y)$ where two vertices $(x,y)$ and $(x',y')$ are adjacent if ($xx' \in E(X)$ and $yy' \in E(Y)$) or ($xx' \in E(\overline{X})$ and $yy' \in E(\overline{Y})$), where $\overline{X}$ and $\overline{Y}$ are the complements of $X$ and $Y$. Probably the most well known property of this product is that the cliques correspond to common induced subgraphs of $X$ and $Y$, but I am interested in the automorphisms of this product.

If $\sigma_1$ and $\sigma_2$ are automorphisms of $X$ and $Y$ respectively, then it is not difficult to see that the map $(x,y) \mapsto (\sigma_1(x), \sigma_2(y))$ is an automorphism of $X \diamond Y$. Let's call this the "Simple Construction". I am wondering when the only automorphisms of $X \diamond Y$ are those from the Simple Construction.

A necessary condition for this is that the graphs are not isomorphic. This is because if $\varphi_1 : V(X) \to V(Y)$ and $\varphi_2 : V(Y) \to V(X)$ are isomorphisms of $X$ and $Y$, then the map $(x,y) \mapsto (\varphi_2(y), \varphi_1(x))$ will be an automorphism of $X \diamond Y$, and this cannot be obtained by the Simple Construction, (the $X$-coordinate of the image depends only on the $Y$-coordinate of the input for this construction).

Moreover, if $\varphi_1$ and $\varphi_2$ are isomorphisms of $X$ and $\overline{Y}$ instead, then the construction above still gives an automorphism of $X \diamond Y$. Thus $X$ and $\overline{Y}$ being non-isomorphic is also a necessary condition for all automorphisms of $X \diamond Y$ to be obtainable from the Simple Construction.

It seems that these two conditions are still not sufficient though. I tested pairs of random regular graphs (of random degrees) on 20 vertices in Sage and found a few examples of graphs $X$ and $Y$ such that $X \not\cong Y$ and $X \not\cong \overline{Y}$ but $X \diamond Y$ had more automorphisms than those from the Simple Construction. In each of these examples at least one of $X$ and $Y$ was a disjoint union of cycles (and the other was of the same form or cubic).

So my question is what additional conditions can I impose on $X$ and $Y$ that will ensure that the only automorphisms of $X \diamond Y$ are those from the Simple Construction? I would prefer something simple such as requiring that $X, Y, \overline{X}, \overline{Y}$ are all connected. Alternatively, are there any good references for automorphisms of this product?

$\endgroup$
1
  • 2
    $\begingroup$ You’re going to need your factors to be “coprime”. For the Cartesian product, recognizing this is doable (but not trivial), I’m not even sure it is doable for the direct product. Your best source of information will be Hammack, Imrich and Klavzar “Handbook of graph products”, but I don’t recall seeing your “modular product” there. $\endgroup$ Commented Dec 12, 2017 at 4:14

0

You must log in to answer this question.

Browse other questions tagged .