An extremal problem in geodetic graphs
type: Item
instance of: scholarly article
title: An extremal problem in geodetic graphs
zbMATH Open document ID: 0537.05029
DOI: 10.1016/0012-365X(84)90112-2
author: N. E. Zubov
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3853107
zbMATH Keywords: geodetic graph
zbMATH Keywords: unique shortest path
zbMATH Keywords: diameter
zbMATH Keywords: geodetic blocks
reviewed by: B. Andrasfai
MaRDI profile type: Publication
cites work: Parallel concepts in graph theory
cites work: Geodetic orientations of complete \(k\)-partite graphs
cites work: A note on geodetic graphs of diameter two and their relation to orthogonal Latin squares
cites work: Some general constructions of geodetic blocks
cites work: Q4116463
cites work: Q4041603
cites work: Geodetic graphs of diameter two
cites work: Q3937451
full work available at URL: 0012-365x(84)90112-2
OpenAlex ID: W1977813728
Recommended article: Q4489242
Recommended article: Q3990579
Recommended article: Extremal problems for geometric hypergraphs
Recommended article: Q4677980
Recommended article: Q3537009
Recommended article: Geodesics in graphs, an extremal set problem, and perfect hash families
Recommended article: A characterization of geodetic graphs
Recommended article: Q3767372
Recommended article: STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS
description: scientific article; zbMATH DE number 3853107