Distinguishing Polynomials of 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_ | 1866929294064746496 |
|---|---|
| author | Haghighi, Mohammad Hassan Shirdareh Ghazanfari, Amir Mohammad Fard, Seyed Ali Reza Talebpour Shirazi |
| author_facet | Haghighi, Mohammad Hassan Shirdareh Ghazanfari, Amir Mohammad Fard, Seyed Ali Reza Talebpour Shirazi |
| contents | For a graph $G$, a $k$-coloring $c:V(G)\to \{1,2,\ldots, k\}$ is called distinguishing, if the only automorphism $f$ of $G$ with the property $c(v)=c(f(v))$ for every vertex $v\in G$ (color-preserving automorphism), is the identity. In this paper, we show that the number of distinguishing $k$-colorings of $G$ is a monic polynomial in $k$, calling it the distinguishing polynomial of $G$. Furthermore, we compute the distinguishing polynomials of cycles and complete multipartite graphs. We also show that the multiplicity of zero as a root of the distinguishing polynomial of $G$ is at least the number of orbits of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19264 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distinguishing Polynomials of Graphs Haghighi, Mohammad Hassan Shirdareh Ghazanfari, Amir Mohammad Fard, Seyed Ali Reza Talebpour Shirazi Combinatorics 05C31, 05C15, 05C30 For a graph $G$, a $k$-coloring $c:V(G)\to \{1,2,\ldots, k\}$ is called distinguishing, if the only automorphism $f$ of $G$ with the property $c(v)=c(f(v))$ for every vertex $v\in G$ (color-preserving automorphism), is the identity. In this paper, we show that the number of distinguishing $k$-colorings of $G$ is a monic polynomial in $k$, calling it the distinguishing polynomial of $G$. Furthermore, we compute the distinguishing polynomials of cycles and complete multipartite graphs. We also show that the multiplicity of zero as a root of the distinguishing polynomial of $G$ is at least the number of orbits of $G$. |
| title | Distinguishing Polynomials of Graphs |
| topic | Combinatorics 05C31, 05C15, 05C30 |
| url | https://arxiv.org/abs/2403.19264 |