A characterization of the set of all shortest paths in a connected graph

Ladislav Nebeský

Mathematica Bohemica (1994)

  • Volume: 119, Issue: 1, page 15-20
  • ISSN: 0862-7959

Abstract

top
Let G be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in G is defined as the set of all paths ξ , then the lenght of ξ does not exceed the length of ς . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : 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.

How to cite

top

Nebeský, Ladislav. "A characterization of the set of all shortest paths in a connected graph." Mathematica Bohemica 119.1 (1994): 15-20. <http://eudml.org/doc/29362>.

@article{Nebeský1994,
abstract = {Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\mathcal \{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 $\mathcal \{L\}$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of $\mathcal \{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.},
author = {Nebeský, Ladislav},
journal = {Mathematica Bohemica},
keywords = {geodetic graphs; connected graph; shortest paths; geodetic graphs; connected graph; shortest paths},
language = {eng},
number = {1},
pages = {15-20},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A characterization of the set of all shortest paths in a connected graph},
url = {http://eudml.org/doc/29362},
volume = {119},
year = {1994},
}

TY - JOUR
AU - Nebeský, Ladislav
TI - A characterization of the set of all shortest paths in a connected graph
JO - Mathematica Bohemica
PY - 1994
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 119
IS - 1
SP - 15
EP - 20
AB - Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $\mathcal {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 $\mathcal {L}$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of $\mathcal {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.
LA - eng
KW - geodetic graphs; connected graph; shortest paths; geodetic graphs; connected graph; shortest paths
UR - http://eudml.org/doc/29362
ER -

References

top
  1. M. Behzad G. Chartrand, L. Lesniak-Foster, Graphs & Digraphs, Prindle, Weber & Schmidt, Boston, 1979. (1979) MR0525578
  2. D.C. Kay, G. Chartrand, 10.4153/CJM-1965-034-0, Canad. J. Math. 17 (1965), 342-346. (1965) Zbl0139.17301MR0175113DOI10.4153/CJM-1965-034-0
  3. H.M. Mulder, The Interval Function of a Graph, Mathematisch Centrum, Amsterdam, 1980. (1980) Zbl0446.05039MR0605838
  4. L. Nebeský, Route systems and bipartite graphs, Czechoslovak Math. Journal 41 (116) (1991), 260-264. (1991) MR1105440

Citations in EuDML Documents

top
  1. Ladislav Nebeský, A characterization of geodetic graphs
  2. Ladislav Nebeský, A characterization of the interval function of a connected graph
  3. Gary Chartrand, Ladislav Nebeský, Ping Zhang, Distance defined by spanning trees in graphs
  4. Ladislav Nebeský, On the set of all shortest paths of a given length in a connected graph
  5. Ladislav Nebeský, Visibilities and sets of shortest paths in a connected graph
  6. Ladislav Nebeský, An algebraic characterization of geodetic graphs
  7. Ladislav Nebeský, A new proof of a characterization of the set of all geodesics in a connected graph
  8. Ladislav Nebeský, Route systems of a connected graph
  9. Ladislav Nebeský, Geodesics and steps in a connected graph
  10. Ladislav Nebeský, On the distance function of a connected graph

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.