Abstract | ||
---|---|---|
Let “ be an infinite, locally finite, connected graph withdistance function δ. Given a ray P in Γ and aconstant C ≥ 1, a vertex-sequence$\{{{x}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VP}}$ is said tobe regulated by C if, for all nεℕ,${{x}}_{{{n}}+{{1}}}$ never precedes xn onP, each vertex of P appears at most C times inthe sequence, and$\delta_{{P}}({{x}}_{{n}},{{x}}_{{{n}}+{{1}}})\leq {{C}}$. R. Halin(Math. Ann., 157, [1964], 125137) defined two rays to beend-equivalent if they are joined by infinitely manypairwise-disjoint paths; the resulting equivalence classes arecalled ends. More recently H. A. Jung (Graph StructureTheory, Contemporary Mathematics, 147, [1993], 477484) defined raysP and Q to be b-equivalent if there existsequences $\{{{x}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VP}}$and $\{{{y}}_{{n}}\}_{{{n}}={{0}}}^\infty\subseteq {{VQ}}$VQ regulated by some constant C e 1 such that$\delta({{x}}_{{n}},{{y}}_{{n}})\leq {{C}}$ for allnεℕ; he named the resulting equivalenceclasses b-fibers. Let $F_0$ denote the set of nondecreasingfunctions from $N$ into the set of positive real numbers. Therelation ${{P}}\sim_{{f}} {{Q}}$ (called f-equivalence)generalizes Jung's condition to$\delta({{x}}_{{n}},{{y}}_{{n}})\leq {{Cf}}({{n}})$. As fruns through $\cal{F}_{{0}}$, uncountably many equivalencerelations are produced on the set of rays that are no finer thanb-equivalence while, under specified conditions, are nocoarser than end-equivalence. Indeed, for every “ thereexists an "end-defining function" ${{f}}\in F_{{0}}$ that isunbounded 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}}\inF_{{0}}$ such that ${{P}}\sim_{{f}} {{Q}}$. The equivalence classeswith respect to $\approx$ are called bundles. We pursue thenotion of "initially metric" rays in relation to bundles, and showthat in any bundle either all or none of its rays are initiallymetric. Furthermore, initially metric rays in the same bundle areend-equivalent. In the case that Γ contains translatable rayswe give some sufficient conditions for every f-equivalenceclass to contain uncountably many g-equivalence classes(where ${lim}_{{{n}}\to\infty}{{g}}({{n}})/{{f}}({{n}})={{0}}$). Weconclude with a variety of applications to infinite planar graphs.Among these, it is shown that two rays whose union is the boundaryof an infinite face of an almost-transitive planar map are neverbundle- equivalent. © 2006 Wiley Periodicals, Inc. J GraphTheory 54: 125153, 2007 |
Year | DOI | Venue |
---|---|---|
2007 | 10.1002/jgt.v54:2 | Journal of Graph Theory |
Keywords | Field | DocType |
constant c,connected graph withdistance function,bundle areend-equivalent,ray p,aconstant c,almost-transitive planar map,infinite face,sublinear function,c time,end-defining function,connected graph,end,distance function,fiber | Sublinear function,Topology,Discrete mathematics,Graph,Combinatorics,Equivalence relation,Vertex (geometry),Positive real numbers,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
54 | 2 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
C. Paul Bonnington | 1 | 100 | 19.95 |
R. Bruce Richter | 2 | 333 | 52.52 |
Mark E. Watkins | 3 | 109 | 32.53 |