An extremal problem in geodetic graphs

DOI10.1016/0012-365X(84)90112-2MaRDI QIDQ792335zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(84)90112-2

zbMATH Keywords

diametergeodetic blocksgeodetic graphunique shortest path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1472187
• scientific article; zbMATH DE number 38308
• Extremal problems for geometric hypergraphs
• Extremal problems for geometric hypergraphs
• scientific article; zbMATH DE number 2170483
• Some results on geodetic number of graphs
• Geodesics in graphs, an extremal set problem, and perfect hash families
• A characterization of geodetic graphs
• scientific article; zbMATH DE number 4025472
• STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS

Cites work

• A note on geodetic graphs of diameter two and their relation to orthogonal Latin squares
• Geodetic graphs of diameter two
• Geodetic orientations of complete k-partite graphs
• scientific article; zbMATH DE number 3754755 (Why is no real title available?)
• scientific article; zbMATH DE number 3455291 (Why is no real title available?)
• scientific article; zbMATH DE number 3540829 (Why is no real title available?)
• Parallel concepts in graph theory
• Some general constructions of geodetic blocks

Cited in

(15)

• Bigeodetic graphs
• Graham's problem on shortest networks for points on a circle
• A new upper bound on the number of edges in a geodetic graph
• scientific article; zbMATH DE number 3875322 (Why is no real title available?)
• scientific article; zbMATH DE number 4214057 (Why is no real title available?)
• scientific article; zbMATH DE number 4045781 (Why is no real title available?)
• A class of geodetic blocks
• scientific article; zbMATH DE number 38308 (Why is no real title available?)
• A note on 3-Steiner intervals and betweenness
• scientific article; zbMATH DE number 1210906 (Why is no real title available?)
• Towards minimumk-geodetically connected graphs
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
• A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs
• On the connectivity and diameter of geodetic graphs
• Geodetic blocks of diameter three

This page was built for publication: An extremal problem in geodetic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792335)