Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs

Josephine Brooks, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, Brendan Rooney and Darren 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-4020, 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 Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
Darren Narayan: School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA

Mathematics, 2021, vol. 9, issue 2, 1-16

Abstract: An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G . The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G . The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph.

Keywords: fixing number; circulant graph; point-block incidence graph; asymmetric graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/2/166/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/2/166/ (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:9:y:2021:i:2:p:166-:d:480532

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 ().