Partial linear spaces and identifying codes

Let (P,L,I)(P,L,I) be a partial linear space and X⊆P∪LX⊆P∪L. Let us denote (X)I=⋃x∈X{y:yIx}(X)I=⋃x∈X{y:yIx} and [X]=(X)I∪X[X]=(X)I∪X. With this terminology a partial linear space  (P,L,I)(P,L,I)is said to admit a  (1,≤k)(1,≤k)-identifying code   if and only if the sets [X][X] are mutually different for all X⊆P∪LX⊆P∪L with ∣X∣≤k∣X∣≤k. In this paper we give a characterization of kk-regular partial linear spaces admitting a (1,≤k)(1,≤k)-identifying code. Equivalently, we give a characterization of kk-regular bipartite graphs of girth at least six admitting a (1,≤k)(1,≤k)-identifying code. Moreover, we present a family of kk-regular partial linear spaces on 2(k−1)2+k2(k−1)2+k points and 2(k−1)2+k2(k−1)2+k lines whose incidence graphs do not admit a (1,≤k)(1,≤k)-identifying code. Finally, we show that the smallest (k;6)(k;6)-graphs known up until now for k−1k−1 where k−1k−1 is not a prime power, admit a (1,≤k)(1,≤k)-identifying code.