On the fixed number of graphs

Document Type : Research Paper


Centre for advanced studies in Pure and Applied Mathematics‎, ‎Bahauddin Zakariya University Multan‎, ‎Pakistan.


‎A set of vertices $S$ of a graph $G$ is called a fixing set of $G$‎, ‎if only the trivial automorphism of $G$ fixes every vertex in $S$‎. ‎The fixing number of a graph is the smallest cardinality of a fixing‎ ‎set‎. ‎The fixed number of a graph $G$ is the minimum $k$‎, ‎such that ‎every $k$-set of vertices of $G$ is a fixing set of $G$‎. ‎A graph $G$‎ ‎is called a $k$-fixed graph‎, ‎if its fixing number and fixed number‎ ‎are both $k$‎. ‎In this paper‎, ‎we study the fixed number of a graph‎ ‎and give a construction of a graph of higher fixed number from a‎ ‎graph of lower fixed number‎. ‎We find the bound on $k$ in terms of‎ ‎the diameter $d$ of a distance-transitive $k$-fixed graph‎.


Main Subjects

N. Biggs, Algebraic Graph Theory, Cambridge Univ. Press, Cambridge, 1993.
D.L. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin. 13 (2006), no. 1, Research Paper 78, 12 pages.
J. Caceres, D. Garijo, M.L. Puertas and C. Seara, On the determining number and the metric dimension of graphs, Electron. J. Combin. 17 (2010), no. 1, Research Paper 63, 20 pages.
D. Erwin and F. Harary, Destroying automorphisms by fixing nodes, Discrete Math. 306 (2006), no. 24, 3244--3252.
C.R. Gibbons and J.D. Laison, Fixing numbers of graphs and groups, Electron. J. Combin. 16 (2009), no. 1, Research Paper 39, 13 pages.
M. Jannesari and B. Omoomi, On randomly k-dimensional graphs, Appl. Math. Lett. 24 (2011), no. 10, 1625--1629.
M. Jannesari and B. Omoomi, Characterization of randomly k-dimensional graphs, Arxiv:1103.3570 [math.CO].
I. Javaid, H. Benish, U. Ali and M. Murtaza, On some automorphism related parameters in graphs, Arxiv:1411.4922 [math.CO].
I. Javaid, M. Fazil, U. Ali and M. Salman, On some parameters related to fixing sets in graphs, submitted.