On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(< r), a nonnegative integer, and n =2r-s+k. The set of r-subsets of [n] = (1, 2, . . . , n) is denoted by vertical bar n vertical bar(r). The generalized Knesergraph K(n,r,s) is the graph whose vertex-set is vertical bar n vertical bar where two r-subsets A and B are joined by an edge if vertical bar A boolean AND B vertical bar <= s. This notedetermines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to [r-s-1/s+k] + 1, which generalizesa resultof Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math 305 (2005) 383-385]. (c) 2007 Elsevier B.V. All rights reserved.