Geodesics in transitive graphs

C. Paul Bonnington, Wilfried Imrich, Norbert Seifter

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


Let P be a double ray in an infinite graph X, and let d and dp denote the distance functions in X and in P respectively. One calls P a geodesic if d(x, y) = dp(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.

Original languageEnglish
Pages (from-to)12-33
Number of pages22
JournalJournal of Combinatorial Theory, Series B
Issue number1
Publication statusPublished - 1 Jan 1996
Externally publishedYes

Cite this