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
    0 references
    intersection numbers
    0 references
    distance-regular graph
    0 references