The determining number of Kneser graphs

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.1--14
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990602
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:28:39
Dernière modification le : jeudi 7 septembre 2017 - 01:03:40
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:39:13

Fichier

2072-7632-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990602, version 1

Collections

Citation

José Cáceres, Delia Garijo, Antonio González, Alberto Márquez, Marıa Luz Puertas. The determining number of Kneser graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.1--14. 〈hal-00990602〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

255