×

An extremal problem in geodetic graphs. (English) Zbl 0537.05029

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.
Reviewer: B.Andrásfai

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Harary, F., Graph-Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[2] Gassman, Larry D.; Entringer, R. C., Geodetic orientations of complete \(k\)-partite graphs, J. Combin. Theory (B), 21, 3, 285 (1975), (Errata) · Zbl 0283.05103
[3] Lee Ho Jin, A note on geodetic graphs of diameter and their relation to orthogonal Latin squares, J. Combin. Theory (B), 22, 2, 165-167 (1977) · Zbl 0373.05060
[4] Parthasarathy, K. R.; Srinivasan, N., Some general construction of geodetic blocks, J. Combin. Theory (B), 33, 2, 121-136 (1982) · Zbl 0488.05056
[5] K.R. Parthasarathy and N. Srinivasan, Geodetic graphs of diameter 3, submitted to Combinatorica.; K.R. Parthasarathy and N. Srinivasan, Geodetic graphs of diameter 3, submitted to Combinatorica.
[6] Plasnik, J., Two constructions of geodetic graphs, Mathematica Slovoca, 27, 65-71 (1977)
[7] Plesnik, J., Strongly geodetic directed graphs. Strongly geodetic directed graphs, Acta Fac. Rerum Natur. Univ. Comenian Math. Publ, 29, 29-34 (1974), znam. · Zbl 0291.05106
[8] Stemple, J. G., Geodetic graphs of diameter two, J. Combin. Theory (B), 17, 266-280 (1974) · Zbl 0323.05122
[9] J.G. Stemple, Geodetic graphs homeomorphic to a complete graph, Annals N.Y. Acad. Sci., 512-517.; J.G. Stemple, Geodetic graphs homeomorphic to a complete graph, Annals N.Y. Acad. Sci., 512-517. · Zbl 0481.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.