Distinguishing chromatic number of middle and subdivision graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910110700273664 |
|---|---|
| author | Banerjee, Amitayu Gopaulsingh, Alexa Molnár, Zalán |
| author_facet | Banerjee, Amitayu Gopaulsingh, Alexa Molnár, Zalán |
| contents | Let $G$ be a simple finite connected graph of order $n$ greater than or equal to $3$. We obtain the following results:
(1). We apply a result of Hamada and Yoshimura from 1976 and some recent results of Alikhani and Soltani (2020) and Kalinowski and Pilsniak (2015) to determine the distinguishing chromatic number of the middle graph $M(G)$ of the graph $G$. In particular, the distinguishing chromatic number $χ_{D}(M(G))$ of the middle graph $M(G)$ of the graph $G$ is $Δ(G)+1$ except for four small graphs $C_{4}, K_{4}, C_{6}$, and $K_{3,3}$, and $Δ(G)+2$ otherwise.
(2). In 2016, Kalinowski, Pilsniak, and Wozniak introduced the total distinguishing number $D''(G)$ of $G$. Inspired by a recent result of Mirafzal (2024), 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{Δ(G)}\rceil$.
(3). We obtain a sharp upper bound for the distinguishing chromatic number of the subdivision graph $S(G)$ of $G$ in terms of the distinguishing number of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07000 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distinguishing chromatic number of middle and subdivision graphs Banerjee, Amitayu Gopaulsingh, Alexa Molnár, Zalán Combinatorics 05C25, 05C15 Let $G$ be a simple finite connected graph of order $n$ greater than or equal to $3$. We obtain the following results: (1). We apply a result of Hamada and Yoshimura from 1976 and some recent results of Alikhani and Soltani (2020) and Kalinowski and Pilsniak (2015) to determine the distinguishing chromatic number of the middle graph $M(G)$ of the graph $G$. In particular, the distinguishing chromatic number $χ_{D}(M(G))$ of the middle graph $M(G)$ of the graph $G$ is $Δ(G)+1$ except for four small graphs $C_{4}, K_{4}, C_{6}$, and $K_{3,3}$, and $Δ(G)+2$ otherwise. (2). In 2016, Kalinowski, Pilsniak, and Wozniak introduced the total distinguishing number $D''(G)$ of $G$. Inspired by a recent result of Mirafzal (2024), 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{Δ(G)}\rceil$. (3). We obtain a sharp upper bound for the distinguishing chromatic number of the subdivision graph $S(G)$ of $G$ in terms of the distinguishing number of $G$. |
| title | Distinguishing chromatic number of middle and subdivision graphs |
| topic | Combinatorics 05C25, 05C15 |
| url | https://arxiv.org/abs/2411.07000 |