2011/11/14 by José Cáceres, J. Cáceres, Cáceres, J. +12 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO
paper · pdf · doi:10.48550/arxiv.1111.3252
arxiv created 2011/11/14 · openalex publication_date 2011/11/14 · arxiv updated 2011/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The 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 Kn:k with n≥ (k(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 Kn:k the determining number is equal to n-k, answering a question posed by Boutin.