Determining Number of Kneser Graphs: Exact Values and Improved Bounds

Abstract

The determining number of a graph $G=(V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs.

arXiv comment9 pages, 1 figure