STABILITY OF GRAPH PAIRS INVOLVING VERTEX-TRANSITIVE GRAPHS

NEW

Problem: For finite simple undirected graphs, with direct product

$$V(\Gamma\times\Sigma)=V(\Gamma)\times V(\Sigma),\qquad (u,i)\sim(v,j)\iff u\sim_\Gamma v\text{ and }i\sim_\Sigma j,$$

a pair $(\Gamma,\Sigma)$ is stable if the natural subgroup $\operatorname{Aut}\Gamma\times\operatorname{Aut}\Sigma\le \operatorname{Aut}(\Gamma\times\Sigma)$ is the whole automorphism group. A graph is $R$-thin if distinct vertices have distinct open neighbourhoods. The conjecture asks:

If $m\ge3$, $\Gamma$ is finite, connected, $R$-thin, coprime to $K_m$ under direct product, and $\operatorname{Aut}\Gamma\ne1$, then $(\Gamma,K_m)$ is stable.

Result: The conjecture is true.

If $\Gamma$ is non-bipartite, then $K_m$ is connected, non-bipartite and $R$-thin, and by the standard direct-product automorphism theorem for coprime $R$-thin non-bipartite products, $(\Gamma,K_m)$ is stable.

Assume now that $\Gamma$ is bipartite, with bipartition $A\cup B$. View $\Gamma$ as the reduced connected bipartite relation $R\subseteq A\times B$. Let $C_m$ be the bipartite relation on two copies of $\{1,\dots,m\}$ given by $i\,C_m\,j\iff i\ne j$. Then the bipartite relation of $\Gamma\times K_m$ is exactly $R\otimes C_m$.

The cardinal-product unique factorisation theorem for finite connected reduced bipartite relations implies that an automorphism of $R\otimes C_m$ can move the $C_m$-factor only to an isomorphic direct factor of $R$ or $R^T$. But $C_m$ is directly prime: if $C_m=P\otimes Q$ with both factors nontrivial, then a row of $P\otimes Q$ would have either $0$ or at least $2$ zero entries, whereas each row of $C_m$ has exactly one zero. Since $\Gamma$ is coprime to $K_m$, neither $R$ nor $R^T$ has a $C_m$-factor. Hence every automorphism of $\Gamma\times K_m$ permutes the layers

$$L_i=V(\Gamma)\times\{i\}.$$

After composing with an automorphism of $K_m$, take an automorphism fixing every $L_i$. Then it has the form

$$(u,i)\mapsto(\alpha_i(u),i)$$

for permutations $\alpha_i$ of $V(\Gamma)$. Since $K_m$ is complete, for all $i\ne j$,

$$u\sim v \iff \alpha_i(u)\sim \alpha_j(v).$$

Thus for fixed $j$ and any $i,k\ne j$,

$$\alpha_j(N_\Gamma(u))=N_\Gamma(\alpha_i(u))=N_\Gamma(\alpha_k(u)).$$

Because $\Gamma$ is $R$-thin, $\alpha_i(u)=\alpha_k(u)$ for every $u$. Since $m\ge3$, all $\alpha_i$ are equal to a single $\alpha\in\operatorname{Aut}\Gamma$. Therefore every automorphism is of the form

$$(u,i)\mapsto(\alpha(u),\tau(i)),$$

with $\alpha\in\operatorname{Aut}\Gamma$ and $\tau\in S_m=\operatorname{Aut}(K_m)$. Hence

$$\operatorname{Aut}(\Gamma\times K_m)=\operatorname{Aut}\Gamma\times\operatorname{Aut}(K_m),$$

so $(\Gamma,K_m)$ is stable.

The assumptions are used essentially: if coprimeness is dropped, $\Gamma=K_2\times K_m$ gives an extra automorphism swapping the two $K_m$-factors.

Citation: Uses the standard unique factorisation theorem for cardinal/direct products of finite connected reduced relations; see R. McKenzie, “Cardinal multiplication of structures with a reflexive relation,” Fund. Math. 70 (1971), 59–101, and W. Imrich–W. Klöckl, “Factoring directed graphs with respect to the cardinal product in polynomial time,” Discuss. Math. Graph Theory 27 (2007), 593–601. Also uses the direct-product automorphism theorem as in Hammack–Imrich–Klavžar, Handbook of Product Graphs, 2nd ed., Theorem 8.18.