Abstract | ||
---|---|---|
Let P be a double ray in an infinite graph X , and let d and d P denote the distance functions in X and in P respectively. One calls P a geodesic if d ( x , y )= d P ( x , y ), for all vertices x and y in P . We give situations when every edge of a graph belongs to a geodesic or a half-geodesic. Furthermore, we show the existence of geodesics in infinite locally-finite transitive graphs with polynomial growth which are left invariant (set-wise) under “translating” automorphisms. As the main result, we show that an infinite, locally-finite, transitive, 1-ended graph with polynomial growth is planar if and only if the complement of every geodesic has exactly two infinite components. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1006/jctb.1996.0031 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
transitive graph,distance function | Discrete mathematics,Combinatorics,Comparability graph,Transitive set,Transitive reduction,Clebsch graph,Transitive closure,Symmetric graph,Geodesic,Mathematics,Transitive relation | Journal |
Volume | Issue | ISSN |
67 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
2 | 0.50 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
C. Paul Bonnington | 1 | 100 | 19.95 |
W. Imrich | 2 | 64 | 20.65 |
N Seifter | 3 | 137 | 26.49 |