Computing the isoperimetric number of a graph
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.
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- scientific article; zbMATH DE number 3891429 (Why is no real title available?)
- scientific article; zbMATH DE number 3989365 (Why is no real title available?)
- Isoperimetric inequalities and Markov chains
- Isoperimetric inequalities, growth, and the spectrum of graphs
- Isoperimetric numbers of graphs
- On the bipartition of graphs
- Some simplified NP-complete graph problems
- The Spectral Radius of infinite Graphs
- Maximum rooted connected expansion
- Lit-only sigma game on a line graph
- Isoperimetric numbers and bisection widths of double coverings of a complete graph.
- On the isoperimetric number of line graphs
- Vertex isoperimetric parameter of a computation graph
- On the complexity of isoperimetric problems on trees
- On the isoperimetric spectrum of graphs and its approximations
This page was built for publication: Computing the isoperimetric number of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1905161)
