Title: Distinguishing Numbers of Graphs
Speaker: Abigail Raz, Rutgers University
Date: Wednesday, March 9, 2016 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Imagine you have a ring of key cards that open various doors. The only problem is that each of your key cards looks exactly the same. You decide to put stickers on them to distinguish the keys, but want to know the minimum number of different stickers you need to do so. This is exactly the problem of the distinguishing number of a graph. Formally we ask what is the minimum number of colors we need so that we can color the vertices of our graph such that no automorphism preserves the coloring. We will discuss this for various graphs and generalize to groups, H, where the distinguishing set of H is the set of distinguishing numbers of graphs G where Aut(G)= H.