Conjecture on automorphisms of graph squares

About 10 years old · traced to

Let GG be a graph, and write G2G^2 for its square, with Aut(G)Aut(G) and Aut(G2)Aut(G^2) denoting their respective automorphism groups. For a connected graph, let dd be its diameter and rr its radius. Automorphism conjecture for graph squares. (i) If GG is a connected graph with diameter dd and radius rr such that r<d⩽2r−2r<d\leqslant 2r-2, then

Aut(G)=Aut(G2).Aut(G)=Aut(G^2).

(ii) If GG is a connected bipartite graph with radius r>2r>2, then

Aut(G)=Aut(G2).Aut(G)=Aut(G^2).

The conjecture concerns the characterization of graphs whose automorphism group is unchanged on passing to the square. The source presents this as an open problem motivated by the belief that most graphs have this property, while noting that previous attempts at a full characterization had failed.

References

Primary source

Saeid Alikhani and Samaneh Soltani, “Distinguishing number and distinguishing index of natural and fractional powers of graphs”, arXiv:1604.03839 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.