Small separations in vertex-transitive graphs

DOI10.1016/J.ENDM.2006.06.042MaRDI QIDQ3439431zbMATH OpenOpenAlexFDO

Authors Matt DeVos, Bojan Mohar

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.4885

zbMATH Keywords

Cayley graphconnectivityexpansiongrowthisoperimetric inequalityvertex-transitive graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: Let $k$ be an integer. We prove a rough structure theorem for separations of order at most $k$ in finite and infinite vertex transitive graphs. Let $G=(V,E)$ be a vertex transitive graph, let $AsubseteqV$ be a finite vertex-set with $|A|le|V|/2$ and $$u sim v$forsome$u in A$$. We show that whenever the diameter of $G$ is at least $31(k+1{)}^2$, either $|A|le2k^3+k^2$, or $G$ has a ring-like structure (with bounded parameters), and $A$ is efficiently contained in an interval. This theorem may be viewed as a rough characterization, generalizing an earlier result of Tindell, and has applications to the study of product sets and expansion in groups.

Recommendations

• On small separations in Cayley and vertex transitive graphs
• Local Expansion of Symmetrical Graphs
• A generalization of a theorem of Diderrich in additive group theory to vertex-transitive graphs
• On small cuts separating an abelian Cayley graph into two equal parts
• On Local Expansion of Vertex-Transitive Graphs

Cites work

• A bound for groups of linear growth
• A note on the growth of transitive graphs
• Connectivity of transitive graphs
• GRAPHS WITH POLYNOMIAL GROWTH
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• Local Expansion of Symmetrical Graphs
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On the Addition of Residue Classes
• On the edge connectivity, Hamiltonicity, and toughness of vertex-transitive graphs
• The Critical Pairs of Subsets of a Group of Prime Order
• Über den Zusammenhang symmetrischer Graphen

Cited in

(3)

• 3-factor-criticality of vertex-transitive graphs
• On small separations in Cayley and vertex transitive graphs
• Local Expansion of Symmetrical Graphs

This page was built for publication: Small separations in vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439431)