On The Fixed Number of Graphs

Abstract

An automorphism on a graph $G$ is a bijective mapping on the vertex set $V(G)$, which preserves the relation of adjacency between any two vertices of $G$. An automorphism $g$ fixes a vertex $v$ if $g$ maps $v$ onto itself. The stabilizer of a set $S$ of vertices is the set of all automorphisms that fix vertices of $S$. A set $F$ is called fixing set of $G$, if its stabilizer is trivial. The fixing number of a graph is the cardinality of a smallest 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 construction of a graph of higher fixed number from graph with lower fixed number. We find bound on $k$ in terms of diameter $d$ of a distance-transitive $k$-fixed graph.

13 pages, 2 figures