On the fixed number of graphs

Document Type : Research Paper

Authors

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

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

Keywords

Main Subjects

References

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.
Bulletin of the Iranian Mathematical Society
Volume 43, Issue 7
December 2017
Pages 2281-2292

Files

History

  • Receive Date: 09 August 2016
  • Revise Date: 02 March 2017
  • Accept Date: 03 March 2017

Share

How to cite

Statistics