A characterization of bipartite graphs associated with BIB-designs with \(\lambda\)=1 (Q1210576): Difference between revisions

Let \(G\) be a finite, undirected, connected graph without loops and multiple edges. Then \(G\) is said to be \(F\)-geodetic for some function \(F\) if the number of shortest paths between two vertices at distance \(i\) is \(F(i)\). Let \(\vartheta\) be a BIB-design. A graph \(G(\vartheta)\) is called associated with \(\vartheta\), if its vertex set is the union of the sets of points and blocks, the adjacency arising from incident points and blocks. It is already known that in the case \(\lambda=1\) and if \(\vartheta\) is not a projective plane, \(G(\vartheta)\) is an example of a bipartite nonregular \(F\)-geodetic graph of diameter 4. In the present paper it is shown that, conversely, every graph with these properties, which is not a tree, can be obtained in this way. Using five lemmas and propositions the author obtains the result that a bipartite \(F\)-geodetic graph \(G\) with diameter \(\leq 4\) is either (i) a tree, or (ii) a distance- regular graph, or (iii) the graph associated with a BIB-design with \(\lambda=1\).