Click here to flash read.
arXiv:2403.19264v1 Announce Type: new
Abstract: 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$.
Click here to read this post out
ID: 809034; Unique Viewers: 0
Unique Voters: 0
Total Votes: 0
Votes:
Latest Change: March 29, 2024, 7:32 a.m.
Changes:
Dictionaries:
Words:
Spaces:
Views: 15
CC:
No creative common's license
No creative common's license
Comments: