Abstract
The fixing number of a graph \(\Gamma \) is the minimum number of vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of \(\Gamma \). This concept was extended to finite groups by Gibbons and Laison. The fixing set of a finite group G is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to G. Surprisingly few fixing sets of groups have been established; only the fixing sets of abelian groups and dihedral groups are completely understood. However, the fixing sets of symmetric groups have been studied previously. In this article, we establish new elements of the fixing sets of symmetric groups by considering line graphs of complete graphs. We conclude by establishing the fixing sets of generalized quaternion groups.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
Data sharing is not applicable to this article as no datasets were generated or analyzed in its production.
References
Anand Kumar, A.: Fundamentals of Digital Circuits, 3rd edn. PHI Learning Pvt Ltd., New Delhi (2014)
Bailey, R.F., Cameron, P.J.: Base size, metric dimension and other invariants of groups and graphs. Bull. Lond. Math. Soc. 43, 209–242 (2011)
Boutin, D.L.: Identifying graph automorphisms using determining sets. Electron. J. Combin. 13(R78), 1–12 (2006)
Cáceres, J., Garijo, D., González, A., Márquez, A., Puertas, M.L.: The determining number of Kneser graphs. Discrete Math. Theor. Comput. Sci. 15(1), 1–14 (2013)
Cameron, P.J., Solomon, R., Turull, A.: Chains of subgroups in symmetric groups. J. Algebra 127, 340–352 (1989)
Eren, T.: Graph invariants for unique localizability in cooperative localization of wireless sensor networks: rigidity index and redundancy index. Ad Hoc Netw. 44, 32–45 (2016)
Erwin, D., Harary, F.: Destroying automorphism by fixing nodes. Discrete Math. 306, 3244–3252 (2006)
Fijavž, G., Mohar, B.: Rigidity and separation indices of graphs in surfaces. Graphs Combin. 26, 491–498 (2010)
Frucht, R.: Herstellung von graphen mit vorgegebener abstrakter gruppe. Compos. Math. 6, 239–250 (1939)
Gibbons, C.R., Laison, J.D.: Fixing numbers of graphs and groups. Electron. J. Combin. 16(R39), 1–13 (2009)
Gilbert, W.J., Nicholson, W.K.: Modern Algebra with Applications, 2nd edn. Wiley, Hoboken (2004)
Gordon, G., McNulty, J., Neudauer, N.A.: Fixing numbers for matroids. Graphs Combin. 32(1), 133–146 (2016)
Graves, C., Graves, S.J., Lauderdale, L.-K.: Smallest graphs with given generalized quaternion automorphism group. J. Graph Theory 87(4), 430–442 (2017)
Javaid, I., Benish, H., Haider, A., Salman, M.: Determining and distinguishing number of hypergraphs. U.P.B. Sci. Bull. Ser. A 76(2), 75–84 (2014)
Koorepanzan-Moftakhar, F., Ashrafi, A.R., Mehranian, Z.: Automorphism group and fixing numbers of (3,6)- and (4,6)-fullerene graphs. Electron. Notes Discrete Math. 45, 113–120 (2014)
Lauderdale, L.-K.: On fixing sets of dihedral groups. Discrete Math. 342(2), 520–528 (2019)
Lynch, K.M.: Determining the orientation of a painted sphere from a single image: a graph coloring problem. CiteSeerX (2001)
Maund, T.: Bases for permutation groups. PhD thesis, University of Oxford (1989)
Sims, C.C.: Computation with permutation groups. In: Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation, SYMSAC 71, pp. 23–28. ACM, New York (1971)
Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932)
Funding
The second author is grateful for the National Science Foundation who partially supported this research through the grant DMS-2136890.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Graves, C., Lauderdale, LK. Fixing Numbers of Graphs with Symmetric and Generalized Quaternion Symmetry Groups. Graphs and Combinatorics 40, 14 (2024). https://doi.org/10.1007/s00373-023-02742-9
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02742-9