-
Small separations in vertex-transitive graphsDeVos, Matt ; Mohar, BojanA 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 contributionPublish date - 2006Language - englishCOBISS.SI-ID - 14068825
Author
DeVos, Matt |
Mohar, Bojan
Topics
matematika |
točkovno tranzitiven graf |
Cayleyjev graf |
rast |
ekspanzija |
izoperimetrična neenakost |
povezanost |
mathematics |
graph theory |
vertex-transitive graph |
Cayley graph |
growth |
expansion |
isoperimetric inequality |
connectivity
source: Electronic notes in discrete mathematics [Elektronski vir]. - ISSN 1571-0653 (Vol. 24, 2006, str. 165-172)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
DeVos, Matt | |
Mohar, Bojan | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.