Characterization of the folded Johnson graphs of small diameter by their intersection arrays (Q1372622)

In the paper the folded Johnson graph \(\overline J(2m,m)\), \(m\geq 4\) an integer, is defined in the following manner: Let \(X\) be a set with \(2m\) elements; the vertices of \(\overline J(2m,m)\) are the partitions of \(X\) into two \(m\)-sets, and two partitions are adjacent if their common refinement is a partition of \(X\) into sets of sizes \(1\), \(1\), \(m-1\), \(m-1\). It is a distance-regular graph with diameter \(d=\left\lfloor{m\over 2}\right\rfloor\) and intersection array \(\{b_0,b_1,\dots, b_{d-1}; c_1, c_2,\dots,c_d\}\), where \(b_i= (m-i)^2\), \(c_i= i^2\) \((0\leq i\leq d-1)\), \(c_d= d^2\), if \(m\) is odd, and \(c_d= 2d^2\), if \(m\) is even. It is known that (i) in the case \(m=4\) there exist more than a thousand distance-regular graphs with the same intersection array as \(\overline J(8,4)\); (ii) the case \(m=5\) is still open; and (iii) in the case \(m\geq 16\) the graphs \(\overline J(2m,m)\) are uniquely determined as distance-regular graphs by their intersection array. Therefore the case \(m\geq 6\) is considered in this paper, and the author gets the result that here holds the same as for \(m\geq 16\), that is, the folded Johnson graphs of diameter \(d\geq 3\) are uniquely determined by their intersection arrays (Theorem 1.1). Since the graph \(\overline J(2m,m)\) induces the \((m\times m)\)-grid graph in the neighbourhood of each vertex, two structural characterizations of such square-grid graphs are given by extensive proofs with many special steps and by using algebraic and combinatorial arguments. The proof of Theorem 1.1 is then a consequence of these characterizations and of some further already known results.