Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
geodetic graphs; connected graph; shortest paths
geodetic graphs; connected graph; shortest paths
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.
References:
[1] M. Behzad G. Chartrand, L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston, 1979. MR 0525578
[2] D.C. Kay, G. Chartrand: A characterization of certain ptolemaic graphs. Canad. J. Math. 17 (1965), 342-346. DOI 10.4153/CJM-1965-034-0 | MR 0175113 | Zbl 0139.17301
[3] H.M. Mulder: The Interval Function of a Graph. Mathematisch Centrum, Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[4] L. Nebeský: Route systems and bipartite graphs. Czechoslovak Math. Journal 41 (116) (1991), 260-264. MR 1105440
Search
Partner of
