Title:

A characterization of the set of all shortest paths in a connected graph (English) 
Author:

Nebeský, Ladislav 
Language:

English 
Journal:

Mathematica Bohemica 
ISSN:

08627959 (print) 
ISSN:

24647136 (online) 
Volume:

119 
Issue:

1 
Year:

1994 
Pages:

1520 
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 nonmetric" 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:

20090924T21:02:18Z 
Last updated:

20200729 
Stable URL:

http://hdl.handle.net/10338.dmlcz/126208 
. 
Reference:

[1] M. Behzad G. Chartrand, L. LesniakFoster: 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), 342346. Zbl 0139.17301, MR 0175113, 10.4153/CJM19650340 
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), 260264. MR 1105440 
. 