An extremal problem in geodetic graphs (Q792335): Difference between revisions
From MaRDI portal
Latest revision as of 09:41, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extremal problem in geodetic graphs |
scientific article |
Statements
An extremal problem in geodetic graphs (English)
0 references
1984
0 references
In a geodetic graph there is a unique shortest path between any two points. The authors give an upper bound for the number of lines in a connected geodetic graph on p points with diameter d. The problem becomes interesting only when we restrict the class to geodetic blocks. (The set of all points with minimum eccentricity lies in a block.) The main result of this paper is an upper bound for the number of lines in this case. In the course of deriving this bound several properties of geodetic blocks have been discovered, which are also of independent interest.
0 references
geodetic graph
0 references
unique shortest path
0 references
diameter
0 references
geodetic blocks
0 references
0 references