A new upper bound for the isoperimetric number of de Bruijn networks
type: Item
instance of: scholarly article
title: A new upper bound for the isoperimetric number of de Bruijn networks
zbMATH Open document ID: 0910.05036
DOI: 10.1016/S0893-9659(97)00111-0
published in: Applied Mathematics Letters
publication date: 1999-04-19T00:00:00Z
review text: The isoperimetric number of a graph is the minimum of \(|\partial S|/| S|\) where \(S\) runs over all vertex sets containing no more than half of the vertices of the graph, and \(\partial S\) denotes ``the boundary,'' which is either the set of all edges leading out of \(S\) (the edge version) or the set of vertices not in \(S\) which have a neighbor in \(S\) (the vertex version). In this paper the vertex version of the isoperimetric number of de Bruijn networks is considered. The author finds an upper bound which is just factor 4 away from the best known lower bound (found by Delorme and Tillich by using eigenvalue techniques).
reviewed by: Bojan Mohar
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1106445
zbMATH Keywords: isoperimetric number
zbMATH Keywords: de Bruijn networks
author: Jörg Bültermann
MaRDI profile type: Publication
cites work: Eigenvalues, eigenspaces and distances to subsets
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Q3907599
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Isoperimetric numbers of graphs
cites work: Eigenvalues, diameter, and mean distance in graphs
cites work: Q4375193
Wikidata QID: Q126377267
description: scientific article; zbMATH DE number 1106445