Intersection numbers of bipartite distance-regular graphs (Q1356549)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intersection numbers of bipartite distance-regular graphs |
scientific article |
Statements
Intersection numbers of bipartite distance-regular graphs (English)
0 references
9 June 1997
0 references
Let \(\Gamma= (X,R)\) denote a finite, connected, undirected graph having vertex set \(X\) and edge set \(R\), and let \(\partial\) denote the distance function on \(\Gamma\). Let \(d\) denote the diameter of the graph \(\Gamma\). For each vertex \(x\) of \(\Gamma\) and each integer \(i\), let \(\Gamma_i(x)= \{y\in X\mid\partial(x,y)= i\}\). The graph \(\Gamma\) is said to be distance-regular with intersection numbers \(c_i\), \(b_i\) \((0\leq i\leq d)\) whenever \(|\Gamma_{i-1}(x)\cap \Gamma_1(y)|= c_i\) and \(|\Gamma_{i+1}(x)\cap \Gamma_1(y)|= b_i\) for all integers \(i\) \((0\leq i\leq d)\) and all \(x,y\in X\) with \(\partial(x,y)= i\). For a bipartite distance-regular graph \(\Gamma\) with intersection numbers \(1= c_1\), \(c_2,\dots,c_d=k\), the author finds a collection of lower bounds for the quantities \(c_{i+1}- 1-c_i(\mu- 1)\), where \(\mu= c_2\). From these bounds it is then deduced that \(c_{i+1}\geq c_i(\mu- 1)+1\) if \(k>c_i\left({(\mu- 1)(\mu-2)(c_i- c_{i-1}-1)\over 2}+1\right)\).
0 references
intersection numbers
0 references
distance-regular graph
0 references