Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
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\).
- On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
- Triangle-free distance-regular graphs with an eigenvalue multiplicity equal to their valency and diameter 3
- Bipartite distance-regular graphs with an eigenvalue of multiplicity \(k\)
- Distance-regular graphs with an eigenvalue \(-k < \theta \leq 2-k\)
- Distance-regular graphs with a relatively small eigenvalue multiplicity
- 2-homogeneous bipartite distance-regular graphs
- Almost 2-homogeneous bipartite distance-regular graphs
- Bipartite distance-regular graphs with an eigenvalue of multiplicity \(k\)
- Completely regular codes
- Cycle-balance conditions for distance-regular graphs
- Eigenvalue multiplicities of highly symmetric graphs
- Hadamard matrices and their applications
- Homogeneous graphs and regular near polygons
- scientific article; zbMATH DE number 43547 (Why is no real title available?)
- scientific article; zbMATH DE number 53885 (Why is no real title available?)
- Problems in algebraic combinatorics
- Spin models on bipartite distance-regular graphs
- Width and dual width of subsets in polynomial association schemes
- Almost 2-homogeneous graphs and completely regular quadrangles
- There are finitely many triangle-free distance-regular graphs with degree 8, 9 or 10
- On bounding the diameter of a distance-regular graph
- Triangle-free distance-regular graphs with an eigenvalue multiplicity equal to their valency and diameter 3
- Triangle-free distance-regular graphs
- A note on triangle-free distance-regular graphs with \(a_2\neq 0\)
- The multiplicity of \(A_{\alpha}\)-eigenvalues of graphs
- On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
- Distance-regular graphs with light tails
This page was built for publication: Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2485947)
