An automorphism is an isomorphism from the vertex set of a graph G to itself. The set of all automorphisms of G together with the operation of composition of functions is called the automorphism group of G, denoted by Aut(G). A 𝑓ixing 𝑠et is a set of vertices to be fixed in G such that the only automorphism possible for the remaining unfixed vertices of G is the identity map. The 𝑓ixing number of a graph, denoted by 𝑓ix(𝐺), is the order of the smallest fixing set. In this paper, we investigate the fixing number of the spanning trees of some special classes of graphs and a simple graph G in general.
Keywords: automorphism, fixing set, fixing numberBoutin, D. (2006). Identifying graph automorphisms using determining sets. Electronic Journal of Combinatorics, 13.
Caceres, J., et al. (2010). On the determining number and metric dimension of graphs. Electronic Journal of Combinatorics, 17.
Cayley, A. (1889). A theorem on trees. Quarterly Journal of Mathematics, 23, 376–378.
Erwin, D., & Harary, F. (2006). Destroying automorphisms by fixing nodes. Discrete Mathematics, 306(24).
Gibbons, C., & Laison, J. (2009). Fixing numbers of graphs and groups. The Electronic Journal of Combinatorics, 16.
Greenfield, K. (2011). The fixing number of a graph. Retrieved from https://web.wpi.edu/Pubs/E-project/Available/E-project-042811-111159/unrestricted/kgreenfield_MQP.pdf
Haghighi, M. H. S., & Bibak, K. H. (2012). The number of spanning trees in some classes of graphs. Rocky Mountain Journal of Mathematics, 42, 1183–1195.
Harary, F. (1998). Graph theory. Addison-Wesley Publishing Company.