Hostname: page-component-7b9c58cd5d-dkgms Total loading time: 0 Render date: 2025-03-15T03:07:04.886Z Has data issue: false hasContentIssue false
  • English
  • Français

On Local Expansion of Vertex-Transitive Graphs

Published online by Cambridge University Press:  01 June 1998

ANDRÁS LUKÁCS
ANDRÁS LUKÁCS
Affiliation:
Computer and Automation Research Institute, Hungarian Academy of Sciences, MTA SZTAKI, Lágymányosi u. 11., H-1111 Budapest, Hungary (e-mail: lukacs@cs.elte.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let X be a vertex-transitive graph and let S be an arbitrary finite subset of its vertices. Denote by @∂S the set of vertices adjacent to S but not in S. Babai and Szegedy proved that for an infinite, connected, locally finite X with subexponential growth we have

formula here

where d(S) is the diameter of S. The aim of this note is to provide a slightly better, tight lower bound on this quantity. We prove that

formula here

under the same conditions.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 2 , June 1998 , pp. 205 - 209
Copyright
1998 Cambridge University Press