Geodesic
A characterization of the set of all shortest paths in a connected graph
Mathematica Bohemica, Tome 119 (1994) no. 1, pp. 15-20

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.1994.126208
Classification : 05C12, 05C38, 05C75
Keywords: geodetic graphs; connected graph; shortest paths 
Nebeský, Ladislav. A characterization of the set of all shortest paths in a connected graph. Mathematica Bohemica, Tome 119 (1994) no. 1, pp. 15-20. doi: 10.21136/MB.1994.126208
@article{10_21136_MB_1994_126208,
     author = {Nebesk\'y, Ladislav},
     title = {A characterization of the set of all shortest paths in a connected graph},
     journal = {Mathematica Bohemica},
     pages = {15--20},
     year = {1994},
     volume = {119},
     number = {1},
     doi = {10.21136/MB.1994.126208},
     mrnumber = {1303548},
     zbl = {0807.05045},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.1994.126208/}
}
TY  - JOUR
AU  - Nebeský, Ladislav
TI  - A characterization of the set of all shortest paths in a connected graph
JO  - Mathematica Bohemica
PY  - 1994
SP  - 15
EP  - 20
VL  - 119
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.1994.126208/
DO  - 10.21136/MB.1994.126208
LA  - en
ID  - 10_21136_MB_1994_126208
ER  - 
%0 Journal Article
%A Nebeský, Ladislav
%T A characterization of the set of all shortest paths in a connected graph
%J Mathematica Bohemica
%D 1994
%P 15-20
%V 119
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.1994.126208/
%R 10.21136/MB.1994.126208
%G en
%F 10_21136_MB_1994_126208

[1] M. Behzad G. Chartrand, L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston, 1979. | MR

[2] D.C. Kay, G. Chartrand: A characterization of certain ptolemaic graphs. Canad. J. Math. 17 (1965), 342-346. | DOI | MR | Zbl

[3] H.M. Mulder: The Interval Function of a Graph. Mathematisch Centrum, Amsterdam, 1980. | MR | Zbl

[4] L. Nebeský: Route systems and bipartite graphs. Czechoslovak Math. Journal 41 (116) (1991), 260-264. | MR

Cité par Sources :