2024/03/28 by Mohammad Hassan Shirdareh Haghighi, Haghighi, Mohammad Hassan Shirdareh, Amir Mohammad Ghazanfari +3
Computer Science · Mathematics · #05C15 #05C30 #05C31 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2403.19264
openalex publication_date 2024/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, a k-coloring c:V(G)→ \1,2,…, k\ is called distinguishing, if the only automorphism f of G with the property c(v)=c(f(v)) for every vertex v∈ 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.