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. This means that, for any two automorphisms s a and b of G, if for each s in S, we have a(s)=b(s), then a=b. The determining number of G is the minimum cardinality of a determining set of G. We study the determining number of Kneser graphs K_{n,k}. In this case, the determining number equals the base size of the symmetric group S_n of degree n in its action on the k-subsets of {1,...,n}, that is, the minimum number of k-subsets such that the only permutation of {1,...,n} that fixes them all is the identity. We prove a formula that allows us to compute the determining number, and hence the base size of this action, for every n and k.

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. This means that, for any two automorphisms s a and b of G, if for each s in S, we have a(s)=b(s), then a=b. The determining number of G is the minimum cardinality of a determining set of G. We study the determining number of Kneser graphs K_{n,k}. In this case, the determining number equals the base size of the symmetric group S_n of degree n in its action on the k-subsets of {1,...,n}, that is, the minimum number of k-subsets such that the only permutation of {1,...,n} that fixes them all is the identity. We prove a formula that allows us to compute the determining number, and hence the base size of this action, for every n and k.

### A formula for computing the exact 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. This means that, for any two automorphisms s a and b of G, if for each s in S, we have a(s)=b(s), then a=b. The determining number of G is the minimum cardinality of a determining set of G. We study the determining number of Kneser graphs K_{n,k}. In this case, the determining number equals the base size of the symmetric group S_n of degree n in its action on the k-subsets of {1,...,n}, that is, the minimum number of k-subsets such that the only permutation of {1,...,n} that fixes them all is the identity. We prove a formula that allows us to compute the determining number, and hence the base size of this action, for every n and k.
##### Scheda Scheda DC
2022
A formula for computing the exact determining number of Kneser graphs
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. This means that, for any two automorphisms s a and b of G, if for each s in S, we have a(s)=b(s), then a=b. The determining number of G is the minimum cardinality of a determining set of G. We study the determining number of Kneser graphs K_{n,k}. In this case, the determining number equals the base size of the symmetric group S_n of degree n in its action on the k-subsets of {1,...,n}, that is, the minimum number of k-subsets such that the only permutation of {1,...,n} that fixes them all is the identity. We prove a formula that allows us to compute the determining number, and hence the base size of this action, for every n and k.
Determining number
Symmetric group
Base size
File in questo prodotto:
File
tesi_triennale_mecenero_2020604.pdf

accesso aperto

Dimensione 261.28 kB