Computing the isoperimetric number of a graph
type: Item
instance of: scholarly article
title: Computing the isoperimetric number of a graph
zbMATH Open document ID: 0835.05041
DOI: 10.1007/BF02366479
published in: Cybernetics and Systems Analysis
publication date: 1996-02-08T00:00:00Z
review text: Let \(G\) be a finite graph. Denote by \(\partial X\), where \(X \subset VG\), the set of edges of the graph \(G\) with one end in \(X\) and the other end in the set \(VG \backslash X\). The ratio \(i(G) = \min |\partial X|/ |X |\), where the minimum is over all nonempty subsets \(X\) of the set \(VG\) such that \(|X |\leq |VG |/2\), is called the isoperimetric number of the graph \(G\). It is easy to see that the isoperimetric number may be used as a ``measure of connectivity'' of the graph. The problem of determining the isoperimetric number is clearly linked with graph partition problems, which often arise in various applications. The isoperimetric number is also important for studying Riemann surfaces. These and other applications of the isoperimetric number justify the analysis of graphs of this kind. The properties of the isoperimetric number are presented in more detail in [(*) \textit{B. Mohar}, J. Comb. Theory, Ser. B 47, No. 3, 274-291 (1989; Zbl 0719.05042)]. A similar construct for infinite graphs has been considered in other papers. It is shown in (*) that the computation of the isoperimetric number is an NP-hard problem for graphs with multiple edges. We show that the decision problem ``given the graph \(G\) and two integers \(s\) and \(t\) decide if \(i(G) \leq s/t\)'' is NP-complete even for simple graphs with vertex degrees not exceeding 3. Note that the isoperimetric number of a tree can be computed by a known polynomial-time algorithm, see the Mohar paper mentioned above.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 830620
zbMATH Keywords: isoperimetric number
zbMATH Keywords: NP-hard problem
author: Petr A. Golovach
MaRDI profile type: Publication
cites work: The Spectral Radius of infinite Graphs
cites work: On the bipartition of graphs
cites work: Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
cites work: Some simplified NP-complete graph problems
cites work: Q3752395
cites work: Q3347934
cites work: Isoperimetric inequalities, growth, and the spectrum of graphs
cites work: Isoperimetric numbers of graphs
cites work: Isoperimetric inequalities and Markov chains
description: scientific article; zbMATH DE number 830620