2014/06/15 by Sylvain Gravier, Gravier, Sylvain, Kahina Meslem +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1406.3844
arxiv created 2014/06/15 · arxiv updated 2014/06/17
Introduced by Albertson et al. \citealbertson, the distinguishing number D(G) of a graph G is the least integer r such that there is a r-labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. Most of graphs studied in literature have 2 as a distinguishing number value except complete, multipartite graphs or cartesian product of complete graphs depending on n. In this paper, we study circulant graphs of order n where the adjacency is defined using a symmetric subset A of ℤn, called generator. We give a construction of a family of circulant graphs of order n and we show that this class has distinct distinguishing numbers and these lasters are not depending on n.