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 ksubsets of {1,...,n}, that is, the minimum number of ksubsets 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 ksubsets of {1,...,n}, that is, the minimum number of ksubsets 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
MECENERO, GIOVANNI
2022/2023
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 ksubsets of {1,...,n}, that is, the minimum number of ksubsets 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.File  Dimensione  Formato  

tesi_triennale_mecenero_2020604.pdf
accesso aperto
Dimensione
261.28 kB
Formato
Adobe PDF

261.28 kB  Adobe PDF  Visualizza/Apri 
The text of this website © Università degli studi di Padova. Full Text are published under a nonexclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/52081