An extremal problem in geodetic graphs (Q792335): Difference between revisions

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.