Previous |  Up |  Next


Title: A characterization of the set of all shortest paths in a connected graph (English)
Author: Nebeský, Ladislav
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 119
Issue: 1
Year: 1994
Pages: 15-20
Summary lang: English
Category: math
Summary: Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\Cal L$ of all shortest paths in $G$ is defined as the set of all paths $\xi$, then the lenght of $\xi$ does not exceed the length of $\varsigma$. While the definition of $\Cal L$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an "almost non-metric" characterization of $\Cal L$: a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem 1. One of them (Theorem 3) gives a characterization of geodetic graphs. (English)
Keyword: geodetic graphs
Keyword: connected graph
Keyword: shortest paths
MSC: 05C12
MSC: 05C38
MSC: 05C75
idZBL: Zbl 0807.05045
idMR: MR1303548
DOI: 10.21136/MB.1994.126208
Date available: 2009-09-24T21:02:18Z
Last updated: 2020-07-29
Stable URL:
Reference: [1] M. Behzad G. Chartrand, L. Lesniak-Foster: Graphs & Digraphs.Prindle, Weber & Schmidt, Boston, 1979. MR 0525578
Reference: [2] D.C. Kay, G. Chartrand: A characterization of certain ptolemaic graphs.Canad. J. Math. 17 (1965), 342-346. Zbl 0139.17301, MR 0175113, 10.4153/CJM-1965-034-0
Reference: [3] H.M. Mulder: The Interval Function of a Graph.Mathematisch Centrum, Amsterdam, 1980. Zbl 0446.05039, MR 0605838
Reference: [4] L. Nebeský: Route systems and bipartite graphs.Czechoslovak Math. Journal 41 (116) (1991), 260-264. MR 1105440


Files Size Format View
MathBohem_119-1994-1_2.pdf 738.7Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo