Automorphism groups and Distinguishing Colorings of Central and Middle Graphs

Let G be a simple, finite, connected, and undirected graph. The middle graph M(G) of G is obtained from the subdivision graph S(G) after joining pairs of subdivided vertices that lie on adjacent edges of G and the central graph C(G) of G is obtained from S(G) after joining all non-adjacent vertices of G. We show that if the order of G is at least 4, then Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic (as abstract groups) and apply these results to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) inspired by an algorithm due to Kalinowski, Pilsniak, and Wozniak from 2016.