•  
  •  
 

Abstract

A graph $G$ is said to be \emph{d-distinguishable} if there exists a not-necessarily proper coloring with $d$ colors such that only the trivial automorphism preserves the color classes. For a 2-distinguishing labeling, the \emph{ cost of $2$-distinguishing}, denoted $\rho(G),$ is defined as the minimum size of a color class over all $2$-distinguishing colorings of $G$. Our work also utilizes \emph{determining sets} of $G, $ sets of vertices $S \subseteq G$ such that every automorphism of $G$ is uniquely determined by its action on $S.$ The \emph{determining number} of a graph is the size of a smallest determining set. We investigate the cost of $2$-distinguishing families of Kneser graphs $K_{n:k}$ by using optimal determining sets of those families. We show the determining number of $\kntwo$ is equal to $\left\lceil{ \frac{2n-2}{3}}\right\rceil$and give linear bounds on $\rho(\kntwo)$ when $n$ is sufficiently sized.

Author Bio

James Garrison graduated summa cum laude from Hampden-Sydney College with a degree in Mathematics and Philosophy at Hampden-Sydney College in Virginia. In the fall of 2022, he will be pursuing a P.hD. in Mathematics at North Carolina State University. He completed this work under the guidance of Dr. Sarah Loeb.

Download

Share

COinS