فهرست نشریات علمی دسترسی آزاد ایران

Let $G$ be a simple finite connected graph of order $n\geq 3$ with maximum degree $\Delta(G)$. In 2016, 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 (3) is sharp: (1) The distinguishing chromatic number $\chi_{D}(M(G))$ of the middle graph $M(G)$ of the graph $G$ is $\Delta(G)+1$ except for four small graphs $C_{4}, K_{4}, C_{6}$, and $K_{3,3}$, and $\Delta(G)+2$ otherwise. (2)  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$. (3) 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 3, then the distinguishing chromatic number $\chi_{D}(S(G))$ of $S(G)$ is at most $D(G)$, and if $D(G)$ is at most $2$, then $\chi_D(S(G))= D(G)+1$. (4) If $D(G)\neq 1$ and $\chi_D(G)=2$, then the automorphism group of $G$ consists of $2$ elements.