Conjecture on automorphisms of graph squares

From papers

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<d2r2r<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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.