Automorphism groups and Distinguishing Colorings of Central and Middle Graphs

Abstract

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 this result to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) and provide examples showing that these bounds cannot be improved in general. Moreover, we use idempotent commutative Latin squares and a theorem of Galvin on list edge colorings of bipartite graphs to study the total distinguishing chromatic number of central graphs.

In this revised version, written and updated by the first author, we include eight figures for the reader's convenience and added a section on total distinguishing coloring of central graphs