A new upper bound for the isoperimetric number of de Bruijn networks (Q1375854)

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).