DIKUL - logo
(UL)
  • Small separations in vertex-transitive graphs
    DeVos, Matt ; Mohar, Bojan, 1956-
    A rough structure theorem for small separations in symmetric graphs is developed. Let ▫$G=(V,E)$▫ be a vertex transitive graph, let ▫$A \subseteq V$▫ be finite with ▫$|A| \le \frac{|V|}{2}$▫ and set ... ▫$k = |\{v \in V \setminus A: u \sim v$▫ for some ▫$u \in A\}|$▫. We show that whenever the diameter of ▫$G$▫ is at least ▫$31(k+1)^2$▫, either ▫$|A| \le 2k^3$▫, or ▫$G$▫ has a (bounded) ring-like structure and ▫$A$▫ is efficiently contained in an interval. This theorem has applications to the study of product sets and expansion in groups.
    Source: Electronic notes in discrete mathematics [Elektronski vir]. - ISSN 1571-0653 (Vol. 24, 2006, str. 165-172)
    Type of material - conference contribution
    Publish date - 2006
    Language - english
    COBISS.SI-ID - 14068825

    Link(s):

    http://dx.doi.org/10.1016/j.endm.2006.06.042

Shelf entry