Hypergraphs for computing determining sets of Kneser graphs

MaRDI QIDQ6229019zbMATH OpenFDO

Authors Jose Cáceres, Delia Garijo, Antonio González, A. Márquez, M. L. Puertas

Publication date 14 November 2011

Abstract: A set of vertices $S$ is a emph{determining set} of a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The emph{determining number} of $G$ is the minimum cardinality of a determining set of $G$. This paper studies determining sets of Kneser graphs from a hypergraph perspective. This new technique lets us compute the determining number of a wide range of Kneser graphs, concretely $K_{n:k}$ with $ngeqfrack(k+1)2+1$. We also show its usefulness by giving shorter proofs of the characterization of all Kneser graphs with fixed determining number 2, 3 or 4, going even further to fixed determining number 5. We finally establish for which Kneser graphs $K_{n:k}$ the determining number is equal to $n-k$, answering a question posed by Boutin.

This page was built for publication: Hypergraphs for computing determining sets of Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6229019)