On the bipartition of graphs (Q796548)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3865319
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the bipartition of graphs |
scientific article; zbMATH DE number 3865319 |
Statements
On the bipartition of graphs (English)
0 references
1984
0 references
cubic graphs
0 references
isoperimetric problems
0 references
eigenvalues of the Laplacian
0 references
0 references
0.7671700716018677
0 references
0.7509645819664001
0 references
0.750062882900238
0 references
0.7497689723968506
0 references
The isoperimetric constant \(i(G)\) of a cubic graph \(G\) is \(i(G)=\min | \partial U| /| U|\) where \(|\cdot|\) is cardinality, \(U\) runs over all subsets of the vertex set \(VG\) satisfying \(| U| \leq \frac12 | VG|\), and \(| \partial U|\) is the number of edges running from \(U\) to the complement \(VG\backslash U\). The spectral theory on Riemann surfaces is used to prove that infinitely many cubic graphs \(G\) exist satisfying \(i(G)\geq 1/128\).
0 references