پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,853 |
| تعداد مقالات | 14,988 |
| تعداد مشاهده مقاله | 41,822,265 |
| تعداد دریافت فایل اصل مقاله | 16,391,743 |
Distinguishing chromatic number of middle and subdivision graphs | ||
| Transactions on Combinatorics | ||
| دوره 15، شماره 3، آذر 2026، صفحه 147-158 اصل مقاله (510.86 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2025.143380.2224 | ||
| نویسندگان | ||
| Banerjee Amitayu* 1؛ Alexa Gopaulsingh2؛ Zalan Molnar2 | ||
| 1Alfred Renyi Institute of Mathematics, Realtanoda utca 13-15, 1053, Budapest, Hungary. | ||
| 2Eotvos Lorand University, Department of Logic, Muzeum krt. 4, 1088, Budapest, Hungary | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| automorphism group؛ distinguishing number؛ distinguishing chromatic number؛ middle graph؛ subdivision graph | ||
| مراجع | ||
|
[1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 no. 1 (1996) Research Paper 18, 17 pp. [7] K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin., 13 no. 1 (2006) Research Paper 16, 19 pp. | ||
|
آمار تعداد مشاهده مقاله: 402 تعداد دریافت فایل اصل مقاله: 221 |
||