DisCoMath Seminar: Symmetry in Point-Block Incidence Graphs
Symmetry in Point-Block Incidence Graphs
Dr. Darren Narayan
Professor
School of Mathematical Sciences, RIT
Register Here for Zoom Link
Abstract:
We present infinite families of graphs G where all symmetries can be removed by fixing a single vertex. That is, mapping any vertex to itself results in the trivial automorphism. These graphs, called point-block incidence graphs, lie at the intersection of graph theory and combinatorial design theory. A point-block incidence graph is a bipartite graph G=(P, B) with a set of point vertices P = {p1,p2,...,pr} and a set of blocks B = {B1,B2,...,Bs} where pi ∈ P is adjacent to Bj ∈ B ⇔ pi ∈ B. 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 and was introduced by Laison, Gibbons, Erwin, and Harary. We present infinite families of graphs with a fixing number of 1, and further fixing any vertex fixes every vertex of the graph. We also show that other point-block incidence graphs can have a high degree of symmetry and a large fixing number as they can be expressed as the disjoint union of copies of P2×Pn, K3,3, or Möbius ladder graphs. This is joint work with Josephine Brooks, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, and Brendan Rooney.
Speaker Bio:
Darren Narayan is Professor of Mathematics and Director of Undergraduate Research at the Rochester Institute of Technology (RIT) and is a Visiting Research Professor at the Rochester Center for Brain Imaging at the University of Rochester. He received his BS in Mathematics at SUNY Binghamton and MS and PhD degrees from Lehigh University. His primary research is in the area of graph theory and has been recently applying mathematical methods to analyze data from functional MRI scans.
Intended Audience:
Undergraduates, graduates, and experts. Those with interest in the topic.
Keep up with DisCoMath Seminars on the DisCoMathS webpage.
Event Snapshot
When and Where
Who
This is an RIT Only Event
Interpreter Requested?
No