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
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