Automorphism groups and Distinguishing Colorings of Central and Middle Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911574975840256 |
|---|---|
| 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, and undirected graph. The middle graph M(G) of G is obtained from the subdivision graph S(G) after joining pairs of subdivided vertices that lie on adjacent edges of G and the central graph C(G) of G is obtained from S(G) after joining all non-adjacent vertices of G.
We show that if the order of G is at least 4, then Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic (as abstract groups) and apply these results to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) inspired by an algorithm due to Kalinowski, Pilsniak, and Wozniak from 2016. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16301 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automorphism groups and Distinguishing Colorings of Central and Middle Graphs Banerjee, Amitayu Gopaulsingh, Alexa Molnár, Zalán Combinatorics Group Theory 05C15 (Primary) 05C25, 05C76 (Secondary) Let G be a simple, finite, connected, and undirected graph. The middle graph M(G) of G is obtained from the subdivision graph S(G) after joining pairs of subdivided vertices that lie on adjacent edges of G and the central graph C(G) of G is obtained from S(G) after joining all non-adjacent vertices of G. We show that if the order of G is at least 4, then Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic (as abstract groups) and apply these results to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) inspired by an algorithm due to Kalinowski, Pilsniak, and Wozniak from 2016. |
| title | Automorphism groups and Distinguishing Colorings of Central and Middle Graphs |
| topic | Combinatorics Group Theory 05C15 (Primary) 05C25, 05C76 (Secondary) |
| url | https://arxiv.org/abs/2507.16301 |