Repositorio de producción científica de la Universidad de Sevilla

The determining number of Kneser graphs


Advanced Search
Opened Access The determining number of Kneser graphs
Show item statistics
Export to
Author: Cáceres González, José
Garijo Royo, Delia
González Herrera, Antonio
Márquez Pérez, Alberto
Puertas González, María Luz
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2013
Published in: . Discrete Mathematics & Theoretical Computer Science 15(1): 1-14 (2013)
Document type: Article
Abstract: 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 the determining number of Kneser graphs. First, we compute the determining number of a wide range of Kneser graphs, concretely Kn:k with n≥k(k+1) / 2+1. In the language of group theory, these computations provide exact values for the base size of the symmetric group Sn acting on the k-subsets of {1,…, n}. Then, we establish for which Kneser graphs Kn:k the determining number is equal to n-k, answering a question posed by Boutin. Finally, we find all Kneser graphs with fixed determining number 5, extending the study developed by Boutin for determining number 2, 3 or 4.
Size: 394.3Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)