zbMATH — the first resource for mathematics

On the bipartition of graphs. (English) Zbl 0544.05038
The isoperimetric constant i(G) of a cubic graph G is \(i(G)=\min | \partial U| /| U|\) where \(|.|\) is cardinality, U runs over all subsets of the vertex set VG satisfying \(| U| \leq {1\over2}| VG|\), and \(| \partial U|\) is the number of edges running from U to the complement V\(G\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\).

05C35 Extremal problems in graph theory
58J50 Spectral problems; spectral geometry; scattering theory on manifolds
Full Text: DOI
[1] Berger, M.; Gauduchon, P.; Mazet, E., Le spectre d’une variété riemannienne, () · Zbl 0141.38203
[2] Buser, P., Cubic graphs and the first eigenvalue of a Riemann surface, Math. Z., 162, 87-99, (1978) · Zbl 0371.53032
[3] Elstrodt, J., Die selbergsche spurformel für kompakte riemannsche flächen, Jber. d. dt. math. ver., 83, (1981), Heft 2 · Zbl 0453.10021
[4] Hejhal, D., Lect. notes in math. 548, ()
[5] Jacquet, H.; Langlands, R., Automorphic forms on GL(2), () · Zbl 0236.12010
[6] Lang, S., Sl_{2}(\(r\)), (1975), Addison-Wesley Reading, MA · Zbl 0311.22001
[7] Sarnak, P., The arithmetic and geometry of some hyperbolic three manifolds, Acta math., 151, 253-295, (1983) · Zbl 0527.10022
[8] Selberg, A., On the estimation of Fourier coefficients of modular forms, (), 1-15
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.