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

    Identifiers