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
      0 references
      1984
      0 references
      cubic graphs
      0 references
      isoperimetric problems
      0 references
      eigenvalues of the Laplacian
      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

      Identifiers