The bisection width of cubic graphs
Authors:
- 1 June 1989
- journal article
- research article
- Published by Cambridge University Press (CUP) in Bulletin of the Australian Mathematical Society
- Vol. 39 (3) , 389-396
Abstract
For a graph G, define the bisection width bw(G) of G as min { eG(A,B): {A,B} partitions V(G) with ‖A| − |B‖ ≤ 1 } where eG(A, B) denotes the number of edges in G with one end in A and one end in B. We show almost every cubic graph G of order n has bw(G) ≥ n/11 while every such graph has bw(G) ≤ (n + 138)/3. We also show that almost every r-regular graph G of order n has bw(G) ≥ crn where cr → r/4 as r → ∞. Our last result is asymtotically correct.Keywords
This publication has 10 references indexed in Scilit:
- Ramanujan graphsCombinatorica, 1988
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978
- Lower Bounds for the Partitioning of GraphsIBM Journal of Research and Development, 1973
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970