Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990602
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:28:39 PM
Last modification on : Thursday, September 7, 2017 - 1:03:40 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:39:13 PM

File

2072-7632-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

José Cáceres, Delia Garijo, Antonio González, Alberto Márquez, Maria Luz Puertas. The determining number of Kneser graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.1--14. ⟨10.46298/dmtcs.634⟩. ⟨hal-00990602⟩

Share

Metrics

Record views

62

Files downloads

1575