✦ LIBER ✦

Geodesics in Transitive Graphs

✍ Scribed by C.Paul Bonnington; Wilfried Imrich; Norbert Seifter

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 541 KB
Volume: 67
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0031

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Geodesics and almost geodesic cycles in

Geodesics and almost geodesic cycles in random regular graphs

✍ Itai Benjamini; Carlos Hoppen; Eran Ofek; Paweł Prałat; Nick Wormald 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d G (u, v) is at least d C (u, v)-e(n). Let (n) be any function tending to infin

Semi-transitive graphs

✍ Steve Wilson 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

## Abstract In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms __bi‐transitive__ and __semi‐transitive__ to describe them. We examine t

Edge-transitive planar graphs

✍ Branko Grünbaum; G. C. Shephard 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 590 KB

Bridged graphs and geodesic convexity

✍ Martin Farber 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 588 KB

A graph G is bridged if each cycle C of length at least four contains two vertices whose distance from each other in G is strictly less than that in C. The class of bridged graphs is an extension of the class of chordal (or triangulated) graphs which arises in the study of convexity in graphs. A se

Long cycles in vertex-transitive graphs

✍ László Babai 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract We prove that every connected vertex‐transitive graph on __n__ ≥ 4 vertices has a cycle longer than (3__n__)^1/2^. The correct order of magnitude of the longest cycle seems to be a very hard question.

Completely Transitive Codes in Hamming G

Completely Transitive Codes in Hamming Graphs

✍ Michael Giudici; Cheryl E. Praeger 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 169 KB

A code in a graph is a non-empty subset C of the vertex set V of . Given C, the partition of V according to the distance of the vertices away from C is called the distance partition of C. A completely regular code is a code whose distance partition has a certain regularity property. A special class