Distinguishing chromatic number of middle and subdivision graphs

Document Type : Research Paper

Authors

1 Alfred Renyi Institute of Mathematics, Realtanoda utca 13-15, 1053, Budapest, Hungary.

2 Eotvos Lorand University, Department of Logic, Muzeum krt. 4, 1088, Budapest, Hungary

Abstract

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.

Keywords

Main Subjects

References

[1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 no. 1 (1996) Research Paper 18, 17 pp.
[2] S. Alikhani and S. Soltani, The chromatic distinguishing index of certain graphs, AKCE Int. J. Graphs Comb., 17 no. 1 (2020) 131–138.
[3] A. Banerjee, Z. Molnár and A. Gopaulsingh, Upper bounds for the list-distinguishing chromatic number, Graphs Combin., 41 no. 3 (2025) Paper No. 59, 17 pp.
[4] A. Banerjee, Z. Molnár and A. Gopaulsingh, Distinguishing colorings, proper colorings, and covering properties without AC, Ars Math. Contemp., 24 no. 4 (2024) Paper No. 6, 18 pp.
[5] A. Banerjee, Z. Molnár and A. Gopaulsingh, Brooks’ type theorems for coloring parameters of locally finite graphs and Kőnig’s Lemma, Ars Math. Contemp., 25 no. 4 (2025) Paper No. 6, 24 pp.
[6] K. L. Collins, M. Hovey and A. N. Trenk, Bounds on the distinguishing chromatic number, Electron. J. Combin., 16 no. 1. (2009) Research Paper 88, 14 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.
[8] T. Hamada and I.Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math., 14 no. 3 (1976) 247–255.
[9] S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim., 9 no. 2 (2024) 297-307.
[10] M. Nihei, On the chromatic number of middle graph of a graph, Pi Mu. Epsilon Journal, 10 no. 9 (1998) 704–708.
[11] R. Kalinowski, M. Pilśniak, M. Woźniak: Distinguishing graphs by total colourings, Ars Math. Contemp., 11 no. 1 (2016) 79–89.
[12] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge-colourings, European J. Combin., 45 (2015), 124–131.
[13] G. Sabidussi: Vertex-transitive graphs, Monatsh. Math., 68 (1964) 426–438.
Transactions on Combinatorics
Volume 15, Issue 3 - Serial Number 3
September 2026
Pages 147-158

Files

History

  • Receive Date: 12 November 2024
  • Revise Date: 02 June 2025
  • Accept Date: 03 June 2025
  • Published Online: 10 November 2025

Share

How to cite

Statistics