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\).
MSC:
| 05C35 | Extremal problems in graph theory |
| 58J50 | Spectral problems; spectral geometry; scattering theory on manifolds |
References:
| [1] | Berger, M.; Gauduchon, P.; Mazet, E., Le spectre d’une variété riemannienne, (Lect. Notes in Math., 194 (1971), Springer: Springer Berlin) · 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, (The Selberg trace formula for PSL \((2, R\), Vol. I (1976), Springer: Springer Berlin) · Zbl 0347.10018 |
| [5] | Jacquet, H.; Langlands, R., Automorphic forms on GL(2), (Lect. Notes in Math., 114 (1970), Springer: Springer Berlin) · Zbl 0236.12010 |
| [6] | Lang, S., \(SL_2(R) (1975)\), Addison-Wesley: 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, (Proceedings of Symposia in Pure Mathematics, Vol. 8 (1965), AMS: AMS Providence, RI), 1-15 · Zbl 0142.33903 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
