Geodetic graphs of diameter two (Q5903898): Difference between revisions

A graph is called geodetic if every two vertices are joined by unique shortest path. \textit{J. G. Stemple} [J. Comb. Theory, Ser. B 17, 266-280 (1974; Zbl 0323.05122)] characterized geodetic graphs G with diameter 2 in terms of three classes: (i) G is a vertex v adjacent to all other vertices of G and each component of G-v is complete, (ii) C is strongly regular with any two nonadjacent vertices having one common neighbor, (iii) Precisely two degrees occur and a certain property obtains. All known examples not of type (i) are described and the problem of proving no other examples exist is posed. New restrictions on the graphs of type (iii) are derived from the spectrum of G.