Premium
Between ends and fibers
Author(s) -
Bonnington C. Paul,
Richter R. Bruce,
Watkins Mark E.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20202
Subject(s) - mathematics , combinatorics , equivalence relation , disjoint sets , vertex (graph theory) , graph , discrete mathematics
Let Γ be an infinite, locally finite, connected graph with distance function δ. Given a ray P in Γ and a constant C ≥ 1, a vertex‐sequence $\{{{x}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VP}}$ is said to be regulated by C if, for all n ϵℕ, ${{x}}_{{{n}}+{{1}}}$ never precedes x n on P , each vertex of P appears at most C times in the sequence, and $\delta_{{P}}({{x}}_{{n}},{{x}}_{{{n}}+{{1}}})\leq {{C}}$ . R. Halin (Math. Ann., 157, 1964, 125–137) defined two rays to be end‐equivalent if they are joined by infinitely many pairwise‐disjoint paths; the resulting equivalence classes are called ends . More recently H. A. Jung (Graph Structure Theory, Contemporary Mathematics, 147, 1993, 477–484) defined rays P and Q to be b‐equivalent if there exist sequences $\{{{x}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VP}}$ and $\{{{y}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VQ}}$ VQ regulated by some constant C ≥ 1 such that $\delta({{x}}_{{n}},{{y}}_{{n}})\leq {{C}}$ for all n ϵℕ; he named the resulting equivalence classes b‐fibers . Let $F_0$ denote the set of nondecreasing functions from $N$ into the set of positive real numbers. The relation ${{P}}\sim_{{f}} {{Q}}$ (called f‐equivalence ) generalizes Jung's condition to $\delta({{x}}_{{n}},{{y}}_{{n}})\leq {{Cf}}({{n}})$ . As f runs through $\cal{F}_{{0}}$ , uncountably many equivalence relations are produced on the set of rays that are no finer than b ‐equivalence while, under specified conditions, are no coarser than end‐equivalence. Indeed, for every Γ there exists an “end‐defining function” ${{f}}\in F_{{0}}$ that is unbounded and sublinear and such that ${{P}}\sim_{{f}} {{Q}}$ implies that P and Q are end‐equivalent. Say ${{P}}\approx {{Q}}$ if there exists a sublinear function ${{f}}\in F_{{0}}$ such that ${{P}}\sim_{{f}} {{Q}}$ . The equivalence classes with respect to $\approx$ are called bundles . We pursue the notion of “initially metric” rays in relation to bundles, and show that in any bundle either all or none of its rays are initially metric. Furthermore, initially metric rays in the same bundle are end‐equivalent. In the case that Γ contains translatable rays we give some sufficient conditions for every f ‐equivalence class to contain uncountably many g ‐equivalence classes (where ${lim}_{{{n}}\to\infty}{{g}}({{n}})/{{f}}({{n}})={{0}}$ ). We conclude with a variety of applications to infinite planar graphs. Among these, it is shown that two rays whose union is the boundary of an infinite face of an almost‐transitive planar map are never bundle‐ equivalent. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 125–153, 2007