GEODETIC RAYS AND FIBERS IN ONE-ENDED PLANAR GRAPHS

A fiber in an infinite graph is an equivalence class of rays whereby t wo rays belong to the same fiber whenever each is contained in an n-ne ighborhood of the other for some n < infinity. As this relation is a r efinement of end-equivalence, it is of interest when applied to one-en ded graphs, in particular to the class G(a,a) of one-ended, 3-connect ed, planar graphs whose valences and covalences are finite and at leas t a and at least a, respectively. Any path in a graph in G(4,4), that uses at most right perpendicular 1/2(rho(f)-2) left perpendicular ed ges of any incident face f (whose covalence is rho(f)) is shown to be the unique geodetic path joining its end-vertices. From this is deduc ed that every edge lies on a geodetic double ray, proving a conjecture of Bonnington, Imrich, and Seifter except in the presence of 3-valent vertices or 3-covalent faces. If all valences are at least 4 and all covalences are at least 6, then all Petrie walks are geodetic double r ays. Basic questions concerning geodetic fibers (i.e., that contain a geodetic ray) in the graphs in G(a,a) are resolved, namely: (1) how m any are there and (2) are they of finite, countable, or uncountable ty pe, i.e., is every set L of geodetic rays in the fiber that is maximal subject to no two rays in L containing a common subray finite, counta ble, or uncountable rrespectively)? A representative result is that gr aphs in G(4,6) boolean OR G(5,4) contain uncountably many geodetic fib ers of finite type; furthermore, every geodetic Fiber in these graphs contains at most three pairwise-disjoint geodetic rays, revealing an u nderlying tree-like structure when growth is exponential. In this vein , it is shown that graphs in G(4,5) boolean OR G(5,4) admit no noniden tity bounded automorphism. (C) 1997 Academic Press.