Geodetic graphs of diameter two (Q5903898): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 03:16, 5 March 2024
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