Distinguishing chromatic number of middle and subdivision graphs

Let G be a simple finite connected graph of order n\geq ۳ with maximum degree \Delta(G). In ۲۰۱۶, Kalinowski, Pil\'{s}niak, and Wo\'{z}niak introduced the total distinguishing number D''(G) of G. We prove the following and show that the upper bound mentioned in (۳) is sharp: (۱) The distinguishing chromatic number \chi_{D}(M(G)) of the middle graph M(G) of the graph G is \Delta(G)+۱ except for four small graphs C_{۴}, K_{۴}, C_{۶}, and K_{۳,۳}, and \Delta(G)+۲ otherwise. (۲)  Inspired by a recent result of Mirafzal, we show that the distinguishing number D(S(G)) of the subdivision graph S(G) of G is D''(G). Consequently, D(S(G)) is at most \lceil \sqrt{\Delta(G)}\rceil. (۳) Let G\not\cong C_{n}, where C_{n} is the cycle graph of order n. If the distinguishing number D(G) of G is at least ۳, then the distinguishing chromatic number \chi_{D}(S(G)) of S(G) is at most D(G), and if D(G) is at most ۲, then \chi_D(S(G))= D(G)+۱. (۴) If D(G)\neq ۱ and \chi_D(G)=۲, then the automorphism group of G consists of ۲ elements.

کلیدواژه ها:

automorphism group ، distinguishing number ، distinguishing chromatic number ، middle graph ، subdivision graph