A note on the growth of transitive graphs

✍ Scribed by W. Imrich; N. Seifter

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 810 KB
• Volume: 73
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90138-0

✦ Synopsis

Let X be a locally finite, connected, growth if and only if X is a strip. infinite, transitive graph. We show that X has linear X(V, E) denotes a graph with vertex-set V(X) and edge-set E(X). Graphs considered in this paper contain neither loops nor mu!tiple edges, AUT(X) denotes the automorphism group of X. We say a subgroup G of AUT(X) acts transitively on X if there is an Q! E G to every x, y E V(X) such that a(x) = y.

Two one-way infinite paths P and Q are equivalent in X, in symbols P hX there is a third path R which meets both of them infinitely often. The equivalence classes with respect to -x are called ends ([5], p. 127). n(E) denotes the maximal number of disjoint one-way infinite paths of an end E E E(X), where E(X) is the set of ends of X. It has been shown by Halin [3,4] that this number always exists.

AutomoThisms not stabilizing any finite, nonempty subgraph are called automorphisms of type 2 by Halin [2; p. 2511. To every automorphism (Y of type 2 there exists an a-invariant two-sided infinite path P ]2; Th. 7j. (A infinite path will be called a 2-path.) Since cy is of type 2 its action on translation. Let v be a vertex of P and P' the one-sided infinite subpath of containing 21, cyu, a%, . . . , etc. Then the end containing P' is called the direction of cy.

The boundary aC of C c V(X) is the set of v adjacent to vertices of C. A connected grap connected set C c V(X) and an automorphis 00, cu(C U K) s C and C\a(C) is finite.