Geodesics in transitive graphs
type: Item
instance of: scholarly article
title: Geodesics in transitive graphs
zbMATH Open document ID: 0856.05032
author: C. Paul Bonnington
author: Wilfried Imrich
author: Norbert Seifter
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-01-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 934802
zbMATH Keywords: distance
zbMATH Keywords: geodesic
zbMATH Keywords: transitive graphs
zbMATH Keywords: polynomial growth
zbMATH Keywords: automorphisms
zbMATH Keywords: planar
MaRDI profile type: Publication
full work available at URL: jctb.1996.0031
OpenAlex ID: W2057392809
DOI: 10.1006/JCTB.1996.0031
description: scientific article; zbMATH DE number 934802