Diestel, Reinhard; Leader, Imre A conjecture concerning a limit of non-Cayley graphs. (English) Zbl 0985.05020 J. Algebr. Comb. 14, No. 1, 17-25 (2001). Graphs \(G\) and \(H\) are quasi-isometric if there exist a function \(\theta:V(G)\to V(H)\) and constants \(C, D\geq 1\) such that for all \(x,y\in V(G)\) and all \(z\in V(H)\) the usual distance metrics in \(G\) and \(H\) satisfy: (1) \(d(\theta x,\theta y)\leq Cd(x,y)\); (2) \(d(x,y)\geq D\) implies \(d(\theta x,\theta y)\leq d(x,y)/C\); and (3) \(d(\theta[V(G)],z)\leq D\). Intuitively, \(G\) and \(H\) “look the same \(\ldots\) from far away.” W. Woess [Discrete Math. 95, No. 1-3, 373-384 (1991; Zbl 0757.05060)] posed the question as to whether every vertex-transitive graph is quasi-isomorphic to some Cayley graph. The present authors construct a sequence of graphs “that seem to look less and less like Cayley graphs.” The sequence converges, in a certain sense, to a 5-valent, 1-ended graph which is conjectured to be a counterexample to Woess’ query. Reviewer’s remark: The volume and paper number of the cited reference by W. Woess are incorrect in the article. The correct numbers appear in this review. Reviewer: Mark E.Watkins (Syracuse) Cited in 3 ReviewsCited in 46 Documents MSC: 05C12 Distance in graphs 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments Keywords:quasi-isometric; quasi-isometry; Cayley graph; line graph Citations:Zbl 0757.05060 PDFBibTeX XMLCite \textit{R. Diestel} and \textit{I. Leader}, J. Algebr. Comb. 14, No. 1, 17--25 (2001; Zbl 0985.05020) Full Text: DOI References: [1] L. Babai, “Vertex-transitive graphs and vertex-transitive maps,” J. Graph Theory15 (1991), 587-627. · Zbl 0743.05020 [2] Gromov, M.; Niblo, G. A. (ed.); Roller, M. A. (ed.), Asymptotic invariants of infinite groups (1993), Cambridge [3] W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory, Dover, New York, 1976. [4] P.M. Soardi and W. Woess, “Amenability, unimodularity, and the spectral radius of random walks on infinite graphs,” Math. Z.205 (1990), 471-486. · Zbl 0693.43001 [5] C. Thomassen and M.E. Watkins, “Infinite vertex-transitive, edge-transitive, non-1-transitive graphs,” Proc. Amer. Math. Soc.105 (1989), 258-261. · Zbl 0677.05042 [6] V.I. Trofimov, “Graphs with polynomial growth,” Math. USSR-Sb. 51 (1985), 405-417. · Zbl 0565.05035 [7] W. Woess, “Topological groups and infinite graphs,” Discrete Math.94 (1991), 1-12. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.