Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency (Q2485947): Difference between revisions

Let \(\Gamma\) be a distance-regular graph with diameter \(d\) and let \(r\in \{1,\dots ,d-1\}\). We say that the parameter \(\gamma_r\) exists if \(|\Gamma(x)\cap \Gamma(y)\cap \Gamma_{r-1}(z)|=\gamma_r\) for all \(x,y\in \Gamma_r(z)\), such that \(d(x,y)=2\). A bipartite distance-regular graph \(\Gamma\) is called (almost) 2-homogeneous, if the parameter \(\gamma_r\) exists for \(r\in \{1,\dots ,d-1\}\) (for \(r\in \{1,\dots ,d-2\}\)). It is known that an eigenvalue multiplicity of a triangle-free distance-regular graph is either 1 or at least valency. If a bipartite distance-regular graph of valency \(k\) has an eigenvalue of multiplicity \(k\), then \(\Gamma\) is 2-homogeneous (Yamazaki). Theorem 2. Let \(\Gamma\) be a triangle- and pentagon-free distance-regular graph with diameter \(d\geq 2\) and valency \(k\). Then \(\Gamma\) has an eigenvalue of multiplicity \(k\) if and only if \(\Gamma\) is one of the following graphs: the \(n\)-gon for \(n\geq 6\); the \(k\)-cube for \(k\geq 2\); the folded \(k\)-cube for \(k\) odd and \(k\geq 7\); the complete bipartite graph \(K_{k+1,k+1}\) minus a matching for \(k\geq 2\); a Hadamard graph or a distance-regular graph with intersection array \(\{k,k-1,k-c,c,1; 1,c,k-c,k-1,k\}\), where \(k=\gamma(\gamma^2+3\gamma+1)\). Theorem 3. A bipartite distance-regular graph with diameter \(d\geq 4\) and valency \(k\) is almost 2-homogeneous if and only if \(\Gamma\) is one of the following graphs: the \(2d\)-gon; the \(d\)-cube; the folded \(2d\)-cube; a generalized 8-gon or 12-gon with order \((1,k-1)\); a Hadamard graph or a distance-regular graph with intersection array \(\{k,k-1,k-c,c,1; 1,c,k-c,k-1,k\}\), where \(k=\gamma(\gamma^2+3\gamma+1)\). In last case there are only two examples known, namely 5-cube for \(\gamma=1\) and bipartite double of the Higman-Sims graph for \(\gamma=2\).