Displaying similar documents to “A characterization of the set of all shortest paths in a connected graph”

Characterizing the interval function of a connected graph

Ladislav Nebeský (1998)

Mathematica Bohemica

Similarity:

As was shown in the book of Mulder [4], the interval function is an important tool for studying metric properties of connected graphs. An axiomatic characterization of the interval function of a connected graph was given by the present author in [5]. (Using the terminology of Bandelt, van de Vel and Verheul [1] and Bandelt and Chepoi [2], we may say that [5] gave a necessary and sufficient condition for a finite geometric interval space to be graphic). In the present paper, the result...

Circular distance in directed graphs

Bohdan Zelinka (1997)

Mathematica Bohemica

Similarity:

Circular distance d ( x , y ) between two vertices x , y of a strongly connected directed graph G is the sum d ( x , y ) + d ( y , x ) , where d is the usual distance in digraphs. Its basic properties are studied.

Graphs S ( n , k ) and a variant of the Tower of Hanoi problem

Sandi Klavžar, Uroš Milutinović (1997)

Czechoslovak Mathematical Journal

Similarity:

For any n 1 and any k 1 , a graph S ( n , k ) is introduced. Vertices of S ( n , k ) are n -tuples over { 1 , 2 , ... , k } and two n -tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs S ( n , 3 ) are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of S ( n , k ) . Together with a formula for the distance, this result is used to compute the distance between two...