An improvement of the Boshier-Nomura bound (Q1328378)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An improvement of the Boshier-Nomura bound
scientific article

    Statements

    An improvement of the Boshier-Nomura bound (English)
    0 references
    0 references
    14 February 1995
    0 references
    Let \(G\) be a connected undirected simple graph. Denote by \(d(u,v)\) the length of a shortest path from \(u\) to \(v\) in \(G\), \(u\), \(v\in V(G)\), and by \(d\) the diameter of \(G\). Let \(G_ i(n)= \{x\in G\mid d(u,x)= i\}\) and \(D^ i_ j(u,v)= G_ i(u)\cap G_ j(v)\). \(G\) is said to be distance- regular if the cardinality of \(D^ i_ j(u,v)\) does not depend on \(u\) and \(v\), but only on \(d(u,v)\). Put \(c_ i= | D^{i-1}_ 1(u,v)|\), \(a_ i= | D^ i_ 1(u,v)|\), \(b_ i= | D^{i+1}_ 1(u,v)|\) \((0\leq i\leq d)\) for arbitrary \(u\) and \(v\) with \(d(u,v)= i\). Let \(k\) be the valency of \(G\). The intersection array of \(G\) is a matrix of type \((3,d+1)\) with columns \((*,0,k)\), \((c_ i,a_ i,b_ i)\), \(1\leq i\leq d-1\), \((c_ d,a_ d,*)\). It is shown that the number of columns \((1,1,k-2)\) in the intersection arrays of distance-regular graphs is at most three if the column \((1,0,k- 1)\) exists. This improves a result of \textit{A. Boshier} and \textit{K. Nomura} [A remark on the intersection arrays of distance-regular graphs, J. Comb. Theory, Ser. B 44, No. 2, 147-153 (1988; Zbl 0595.05048)].
    0 references
    Boshier-Nomura bound
    0 references
    circuit
    0 references
    circuit-chassing technique
    0 references
    diameter
    0 references
    intersection array
    0 references
    distance-regular graphs
    0 references

    Identifiers