The Cost of 2-Distinguishing Hypercubes

Speaker: Debra Boutin

Date: Thu, Oct 29, 2020

Location: Zoom, PIMS, University of Victoria

Subject: Mathematics

Class: Scientific


The distinguishing number of a graph is the smallest number of colors necessary to color the vertices so that no nontrivial automorphism preserves the color classes. If a graph can be distinguished with two colors, the distinguishing cost is the smallest possible size of a color class over all 2-distinguishing colorings. In this talk I will present the long-sought-after (at least by me, :-) ) cost of 2-distinguishing hypercubes. We will begin the talk with definitions and intuitive examples of distinguishing and of cost, cover a bit of history, and work our way to a new technique using binary matrices. Then will we be able to state and understand the new results on hypercubes.