Neighbour-transitive codes in Kneser graphs

A code C is a subset of the vertex set of a graph and C is sneighbour-transitive if its automorphism group Aut(C) acts transitively on each of the first s + 1 parts C0, C1, . . . , Cs of the distance partition {C = C0, C1, . . . , C rho}, where rho is the covering radius of C. While codes have traditionally been studied in the Hamming and Johnson graphs, we consider here codes in the Kneser graphs. Let 12 be the underlying set on which the Kneser graph K(n, k) is defined. Our first main result says that if C is a 2-neighbour-transitive code in K(n, k) such that C has minimum distance at least 5, then n = 2k + 1 (i.e., C is a code in an odd graph) and C lies in a particular infinite family or is one particular sporadic example. We then prove several results when C is a neighbourtransitive code in the Kneser graph K(n, k). First, if Aut(C) acts intransitively on 12 we characterise C in terms of certain parameters. We then assume that Aut(C) acts transitively on 12, first proving that if C has minimum distance at least 3 then either K(n, k) is an odd graph or Aut(C) has a 2homogeneous (and hence primitive) action on 12. We then assume that C is a code in an odd graph and Aut(C) acts imprimitively on 12 and characterise C in terms of certain parameters. We give examples in each of these cases and pose several open problems. (c) 2023 Elsevier Inc. All rights reserved.