On the fixed number of graphs

Abstract

‎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‎.