An isoperimetric problem in Cayley graphs
type: Item
instance of: scholarly article
title: An isoperimetric problem in Cayley graphs
zbMATH Open document ID: 0936.05054
author: Yahya Ould Hamidoune
author: Oriol Serra
author: Anna Lladó
published in: Theory of Computing Systems
publication date: 2000-05-18T00:00:00Z
review text: A graph \(\Gamma\) is said to be \(k\)-separable if there is a subset \(X\) of \(V\) such that \(|X|\geq k\) and \(|\delta X|\geq k\). If \(\Gamma\) is \(k\)-separable, the \(k\)-isoperimetric number of \(\Gamma\) is \(\kappa_k(\Gamma)= \min\{|\delta X|:|X|\geq k\) and \(|\delta X|\geq k\}\). The authors develop a method to study \(k\)-isoperimetric numbers of Cayley graphs. The main result is the following theorem: Let \(T\) be a minimal generating set of a group \(G\) and \(\Gamma= \text{Cay}(G, T\cup T^{-1})\). If \(\Gamma\) is 2-separable, then one of the following conditions holds: (i) \(\kappa_2(\Gamma)= d_2(\Gamma)\), where \(d_2\) is the minimal cardinality of the boundary of two points. (ii) \(\Gamma\) is regular of degree 4 and \(T= \{s,t\}\) with \(s^3= t^3= 1\) and \((st^{-1})^2= 1\). Thus, if \(|S|> 4\), every cutset of cardinality less than \(d_2\) must isolate a single vertex.
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 1383544
zbMATH Keywords: isoperimetric problem
zbMATH Keywords: \(k\)-separable
zbMATH Keywords: Cayley graphs
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
full work available at URL: s002240000129
OpenAlex ID: W2061818328
DOI: 10.1007/S002240000129
description: scientific article; zbMATH DE number 1383544