Characterization of the folded Johnson graphs of small diameter by their intersection arrays
type: Item
instance of: scholarly article
title: Characterization of the folded Johnson graphs of small diameter by their intersection arrays
zbMATH Open document ID: 0884.05077
author: Klaus Metsch
published in: European Journal of Combinatorics
publication date: 1998-04-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05E30
zbMATH DE Number: 1088581
zbMATH Keywords: folded Johnson graph
zbMATH Keywords: distance-regular graph
zbMATH Keywords: diameter
zbMATH Keywords: intersection array
zbMATH Keywords: characterizations
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: eujc.1997.0143
OpenAlex ID: W2000435950
DOI: 10.1006/EUJC.1997.0143
description: scientific article; zbMATH DE number 1088581