## 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.

## Faculty Sponsor

Dr. Sarah Loeb

## Recommended Citation

Garrison, James E.
(2023)
"The Determining Number and Cost of 2-Distinguishing of Select Kneser Graphs,"
*Rose-Hulman Undergraduate Mathematics Journal*: Vol. 24:
Iss.
1, Article 1.

Available at:
https://scholar.rose-hulman.edu/rhumj/vol24/iss1/1