Using determining sets to distinguish Kneser graphs

Michael O. Albertson ; Debra L. Boutin

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

This work introduces the technique of using a carefully chosen determining set to prove the existence of a distinguishing labeling using few labels. A graph $G$ is said to be $d$-distinguishable if there is a labeling of the vertex set using $1, \ldots, d$ so that no nontrivial automorphism of $G$ preserves the labels. A set of vertices $S\subseteq V(G)$ is a determining set for $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. We prove that a graph is $d$-distinguishable if and only if it has a determining set that can be $(d-1)$-distinguished. We use this to prove that every Kneser graph $K_{n:k}$ with $n\geq 6$ and $k\geq 2$ is $2$-distinguishable.

Détail

DOI : 10.37236/938

Classification : 05C78, 05C25
Mots-clés : distinguishing labeling