Geodetic graphs of diameter two (Q5903898)
From MaRDI portal
scientific article; zbMATH DE number 4091545
Language | Label | Description | Also known as |
---|---|---|---|
English | Geodetic graphs of diameter two |
scientific article; zbMATH DE number 4091545 |
Statements
Geodetic graphs of diameter two (English)
0 references
1988
0 references
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.
0 references
unique shortest path
0 references
geodetic graphs
0 references