Fixing Numbers of Point-Block Incidence Graphs

Josephine Brooks, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, Brendan Rooney and Darren A. Narayan ()
Additional contact information
Josephine Brooks: Department of Mathematics, University of Toronto, Toronto, ON M5S 2E4, Canada
Alvaro Carbonero: Department of Mathematical Sciences, University of Nevada, Las Vegas, NV 89154, USA
Joseph Vargas: Mathematical Sciences Department, State University of New York, Fredonia, NY 14063, USA
Rigoberto Flórez: Department of Mathematical Sciences, The Citadel, Charleston, SC 29409, USA
Brendan Rooney: School of Mathematical and Statistical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
Darren A. Narayan: School of Mathematical and Statistical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA

Mathematics, 2023, vol. 11, issue 6, 1-9

Abstract: A vertex in a graph is referred to as fixed if it is mapped to itself under every automorphism of the vertices. The fixing number of a graph is the minimum number of vertices, when fixed, that fixes all of the vertices in the graph. Fixing numbers were first introduced by Laison and Gibbons, and independently by Erwin and Harary. Fixing numbers have also been referred to as determining numbers by Boutin. The main motivation is to remove all symmetries from a graph. A very simple application is in the creation of QR codes where the symbols must be fixed against any rotation. We determine the fixing number for several families of graphs, including those arising from combinatorial block designs. We also present several infinite families of graphs with an even stronger condition, where fixing any vertex in a graph fixes every vertex.

Keywords: fixing number; graph automorphism (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/6/1322/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/6/1322/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:6:p:1322-:d:1092183

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().